how to understand recursion

condor888
condor888 used Ask the Experts™
on
I’ve been always having trouble to understand recursion. I know how to write some simple ones though.

Take this sum calculation Scala program for example. Please don’t answer this question based on the Scala specific implementation. I’d like to have a generic understanding on recursion.

recursion.png
1. It is calling sum(n-1) inside sum(n). Are they (sum(n) and sum(n-1)) using different instance of the same function?
2. How can the compiler understand this function when it is calling itself (sort of unfinished based on my view)?
3. What is the normal procedure of writing recursive functions (design recursive algorithms)?

Thank you!
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Russ SuterSenior Software Developer
Commented:
Recursion is an incredible tool in the right circumstances but has the potential for being seriously abused. One of the best examples of bad recursion is the classic Fibbonacci recursive solution.

That being said there are some applications for which recursion is ideally suited. One common example is traversing a tree.

For a recursive function to work properly it needs two main components: (1) a logical loop and (2) a terminating case. Without a terminating case or a properly constructed terminating case you can run into endless recursion (which isn't truly endless because it doesn't take long for it to eat up all available memory and crash).

To answer your questions...

1. You can call any function from within any other function. In this case sum is calling itself with a new value. In your above case if n == 1 then the recursion stops and the function starts backing out of itself.
2. The machine running the code basically pushes a new instance of the function sum() onto the stack when it needs one. Once the function is complete it pops the item off the top of the stack until it gets back to the base call. Here's a quick illustration of how a recursive function would look on a stack:
                                               
                                                                sum(1)
                                                sum(2)    sum         sum
                                sum(3)    sum        sum         sum        sum
                sum(4)    sum        sum        sum         sum        sum        sum
sum(5)    sum        sum        sum         sum        sum        sum        sum        sum

It's crude but the idea is that each call pushes a copy of "sum" onto the stack until the terminating condition is reached. Once that happens it starts popping those instances off the stack until it unravels completely and returns to the base call.

3. I'm not sure what you mean by "normal procedure".  You do have to be VERY careful when writing a recursive function taking (at least) the following things into account:

    a. Can this be done (viably) using an iterative approach rather than a recursive approach? If the answer is yes, don't use recursion.
    b. Is there a guaranteed terminating condition (i.e. one in which the recursive function is guaranteed not to call itself)?
    c. What are the costs of implementing your code recursively? Recursion is memory hungry (and usually slower than an iterative approach) due to the above described stack calls.
Dave BaldwinFixer of Problems
Most Valuable Expert 2014

Commented:
What Russ ^^^ said.  The first most important thing is to know how to end it.  What is the 'terminating condition'.
This is a related question, in which I posted comments and a helpful link.
Learn Ruby Fundamentals

This course will introduce you to Ruby, as well as teach you about classes, methods, variables, data structures, loops, enumerable methods, and finishing touches.

Author

Commented:
@Russ Suter, thanks for your answer, however, I didn't quite understand why you draw your illustration in a triangle shape. Could you please explain a little bit?

Also, since all recursion can be written in a iterative approach, how can I determine in which case it is viable to use recursion?
Russ SuterSenior Software Developer

Commented:
Look for the iterative approach. Recursion is often the easy way out but it comes at a cost of speed and memory resources.

The triangle was to illustrate how the function gets pushed onto the stack. Each column represents the next stack call. The recursive function sum(5) gets called which calls sum(4) and so on. When it reaches sum(1) then the terminating condition is met and the function is no longer called so the machine starts popping items off the stack.

These videos might be helpful.

https://www.youtube.com/watch?v=Mv9NEXX1VHc
https://www.youtube.com/watch?v=7t_pTlH9HwA

This article also does a fairly good job of explaining the basics using 3 of the most classic examples of recursion.

https://sleeplessafternoon.wordpress.com/2013/03/26/examples-of-recursion-the-good-the-bad-and-the-silly/
Top Expert 2013

Commented:
Hi condor,

simple definition for recursive function for you ... here you go ...

A recursive function is a function that calls itself during its execution. This enables the function to repeat itself several times, outputting the result and the end of each iteration. Below is an example of a recursive function.

Enjoy learning ...
Top Expert 2016
Commented:
to add to above comments:

the assignments performed for sum(100) are

sum(100) = (100 + sum(99))
sum(99)   = (99 + sum(98))
sum(98)   = (98 + sum(97))
....
sum(2) = (2 + sum(1))
sum(1) = (1)

Open in new window


if you put all together into one line

sum(100) = (100 + (99 + (98 + (97 + (..... + (2 + 1))))).....))  

Open in new window


what obviously is the adding all numbers from 100 to 1 and is equivalent to the following loop

sum = 0
for n = 100 to n = 1  
    do 
          sum = sum + n
    end do
    n = n - 1
end for

Open in new window


from the above  you see that all recursive algorithms could be alternatively solved by suitable loops. however, recursion might require much less code and therefore is more elegant. you can see this from another sample already mentioned by Russ the traversing of a tree.

assume a binary tree like the following:

                              F
                          /       \
                       D            G
                    /    \           \
                  B       E           H
                /    \               /  
               A      C            I 

Open in new window

   

if you want to traverse it in alphabetical order you would start at F node go left until A, then print A, go back to B, print B, go right to C, print C, go back to C, go back to D, print D, go right to E, print E, and so on.

obviously the way depends on whether there are left or right child nodes, and the way back to parent nodes may go over two or more steps if you return from a right leaf node. if doing the traversion with a loop you have to memorize all parent nodes for any child node in order to be able to continue the traversion after visiting a right child leaf.

by using recursion, the traversion is much simpler since each node of the tree could be seen as the root node of a sub tree. hence the traversion of the F node actually is to perform traversion of the D node going back to F, print F, and then traverse the G node.

so you have a traverse function like

traverse (node n)
{
      if n == nil return
      traverse (n.left)
      print(n.data) 
      traverse (n.right)
}

Open in new window


which  would be called intially like

node root = tree.root   // read F
traverse(root)

Open in new window


Sara
Let me offer a non-computer-related example of recursion. English teachers often tell us not to define a word in terms of itself, but I submit that there are exceptions. Two of these exceptions are "ancestor" and "descendant." If you ask someone who his ancestors are, he is likely to say something like, "My parents, my grandparents, my great-grandparents, and so on." The "and so on" is inexact, but the only alternative is to continue listing "greats" back to the beginning of time. A more precise definition uses recursion: "My ancestors are my mother, my father, and their ancestors." Notice that there's a tree involved here, just as there is in the computer-related examples given above.

If you really want to understand the entire concept of recursion, read _Gödel, Escher, Bach: An Eternal Golden Braid_ by Douglas Hofstadter.

Author

Commented:
@GuruJava, I am sorry but I didn't see your example.

Author

Commented:
@historychef, interesting!
Dave BaldwinFixer of Problems
Most Valuable Expert 2014

Commented:
That's an interesting book.  It's been a long time since I read it though.
1. Yes. It's a different instance, so it has its own variables in its own memory. Hence memory usage increases the deeper the recursive calls go.

2. Since "dim sum (n: Int);" has already been processed by the compiler, everything needed for "n + sum(n - 1)" is already defined. The compiler only needs to know the prototype for sum(). It doesn't need to know the instructions contained within sum(). It needs to know the instructions to compile sum(), but not just to reference sum(). A reference only needs a matching prototype.

3. "Normal" procedure? There is no "normal" procedure. There are a couple methods of defining and structuring recursive functions so that they're almost guaranteed to give expected and correct results. But after 40+ years as a programmer, I can assert that many different developers have their own methods. (Some of them seem never to figure it out.)

As others have noted, basic iteration is the foundation of recursion. Attempt to write it as a straight iterative procedure first. If it comes out cleanly, then recursion isn't called for. If you find that you need to create new instances of variables for each pass through the loop, then that's a possible indication that recursion might be useful.

And when writing iteration, you might start by attempting to write it as straight in-line code first. If you find that you're simply coding the same statements with the same variables over and over, then that's a probable indication that iteration might be useful.

But a "normal" procedure is going to be the one that works for you once you're comfortable that recursion is clear to you.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial