mohamed.ramadan__'s blog

recursive problem
By mohamed.ramadan__, history, 19 months ago, In English

As a beginner, I face lots of difficulties thinking a program recursively. After thinking for a while, I can tell the output of a recursive function but when I try to write a program recursively on my own, my head gets messy and I can't think properly after some time. I want to know how to think a program recursively in an intuitive way so that I can write a recursive program without thinking recursive tree or call stack every time. How do you think when you write a complex recursive solution?

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
19 months ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

Divide and conquer algorithm and incremental algorithm are types of algorithms that usually come with recursive functions. In this sense, There are several general tips I may offer:

  1. Get clear about what you have got. You can do this by describing your function in a mathematical way, such as using notations like $$$f(x,y)$$$. For example, in the well-known algorithm, mergesort, you can write the function down like $$$\text{MergeSort}(A)$$$, where the argument refers to a sequence $$$A$$$ you have, which you are going to sort.

  2. Get clear about what you want your function to put out. In the mergesort case, when you call $$$\text{MergeSort}(A)$$$, you want to sort the elements in $$$A$$$. So, the output of this function should be the sorted $$$A$$$. This is especially essential because it can help you to get rid of imagining large recursive tree in your mind -- you can simply skip it by knowing what the outcome will exactly be.

  3. Think over what you should do in one step. Either a D&C algorithm or a incremental algorithm focuses on separating a complex problem into several small and easy-to-handle steps, so it's important to get clear about these steps. Take mergesort as an example again. Since it's a D&C algorithm, so when we are dealing with $$$\text{MergeSort}(A)$$$, we must think about:

  • What should we do to divide the problem into small parts? In this case, it's easy. let $$$n$$$ be the number of elements in $$$A$$$, and number the elements in $$$A$$$ from $$$1$$$. We just need to take the middle point $$$m=\lfloor\frac{n+1}{2}\rfloor$$$, and the sequence is naturally divided into two parts, that is $$$A_L=[A_1,A_1,\dots,A_{m}]$$$ and $$$A_R=[A_{m+1},A_{m+2},\dots,A_{n}]$$$.

  • What will happen if we call the function recursively? In this case, we will call function $$$\text{MergeSort}(A_L)$$$ and $$$\text{MergeSort}(A_R)$$$ to get $$$A'_L=\text{MergeSort}(A_L)$$$ and $$$A'_R=\text{MergeSort}(A_R)$$$ respectively. As we have already known, $$$A'_L$$$ and $$$A'_R$$$ are both sorted sequences.

  • What should we do to conquer the result of the sub-problems? Here, we've got $$$A'_L$$$ and $$$A'_R$$$, two sorted halves of original $$$A$$$, so the aim of conquering part is to merge two sorted sequences into one sorted sequence. Details of merging are skipped.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    is there any list of problems that use recursions?

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You can find some by attaching dfs and similar, divide and conquer or data structure tags to your search restrictions since these are algorithms that have heavy reliance on recursions.

      But I have no idea if there are available problem lists focusing on recursions. Luckily, recursive algorithms are so common that you can encounter a number of problems needing recursions just when you are solving problems on CodeForces.

      → Reply