Understanding how recursive functions work

Question

As the title explains I have a very fundamental programming question which I have just not been able to grok yet. Filtering out all of the (extremely clever) "In order to understand recursion, you must first understand recursion." replies from various online threads I still am not quite getting it.

Understanding that when faced with not knowing what we don't know, we can tend to ask the wrong questions or ask the right questions incorrectly I will share what I "think" my question is in hopes that someone with a similar outlook can share some bit of knowledge that will help turn on the recursive light bulb for me!

Here is the function (the syntax is written in Swift):

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a: a + 1, b: b)
    }
}

We'll use 2 and 5 as our arguments:

println(sumInts(a: 2, b: 5))

Obviously the answer is 14. But I'm not clear on how that value is achieved.

These are my 2 hangups:

1. The function is called recursively until a condition is met. That condition is a > b. When this condition is met, return 0. At first glance, I would expect the return value to be 0 which is obviously incorrect.

2. Printing out the value of 'a' on each iteration yields a value which I would expect: 2, 3, 4, 5 (at which point 5+1 > b which meets the first condition: a > b) but I still don't see how the value of 14 is achieved.

My first thought is that something similar to the following is happening magically:

var answer = a;
answer += a+1 until a > b;
return answer;   

So ruling out magic, I'm just not getting something. I would love to understand what's happening more than just implicitly.

If someone could kindly explain what technically happens during this kind of function and why the result isn't 0 and how, eventually, a + sumInts(a: a + 1, b: b) = 14, I would be forever in your debt.

Answer 1

Think recursion as a multiple clones doing same thing...

You ask to clone[1]: "sum numbers between 2 and 5"

+ clone[1]               knows that: result is 2 + "sum numbers between 3 and 5". so he asks to clone[2] to return: "sum numbers between 3 and 5"
|   + clone[2]           knows that: result is 3 + "sum numbers between 4 and 5". so he asks to clone[3] to return: "sum numbers between 4 and 5"
|   |   + clone[3]       knows that: result is 4 + "sum numbers between 5 and 5". so he asks to clone[4] to return: "sum numbers between 5 and 5"
|   |   |   + clone[4]   knows that: result is 5 + "sum numbers between 6 and 5". so he asks to clone[5] to return: "sum numbers between 6 and 5"
|   |   |   |   clone[5] knows that: he can't sum, because 6 is larger than 5. so he returns 0 as result.
|   |   |   + clone[4]   gets the result from clone[5] (=0)  and sums: 5 + 0,  returning 5
|   |   + clone[3]       gets the result from clone[4] (=5)  and sums: 4 + 5,  returning 9
|   + clone[2]           gets the result from clone[3] (=9)  and sums: 3 + 9,  returning 12
+ clone[1]               gets the result from clone[2] (=12) and sums: 2 + 12, returning 14

and voilá!!

Answer 2

I was having hard time to understanding recursion then i found this blog and i already seen this question so i thought i must have to share . You must read this blog i found this extremely helpful it explain with stack and even it explain how two recursion works with stack step by step. I recommend you first understand how stack works which it explain very well here : journey-to-the-stack

then now you will understand how recursion works now take a look of this post : Understand recursion step by step

Its a program :

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(3)

Answer 3

You've got some good answers here so far, but I'll add one more that takes a different tack.

First off, I have written many articles on simple recursive algorithms that you might find interesting; see

http://ericlippert.com/tag/recursion/

http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

Those are in newest-on-top order, so start from the bottom.

Second, so far all of the answers have described recursive semantics by considering function activation. That each, each call makes a new activation, and the recursive call executes in the context of this activation. That is a good way to think of it, but there is another, equivalent way: smart text seach-and-replace.

Let me rewrite your function into a slightly more compact form; don't think of this as being in any particular language.

s = (a, b) => a > b ? 0 : a + s(a + 1, b)

I hope that makes sense. If you're not familiar with the conditional operator, it is of the form condition ? consequence : alternative and its meaning will become clear.

Now we wish to evaluate s(2,5) We do so by doing a textual replacing of the call with the function body, then replace a with 2 and b with 5:

s(2, 5) 
---> 2 > 5 ? 0 : 2 + s(2 + 1, 5)

Now evaluate the conditional. We textually replace 2 > 5 with false.

---> false ? 0 : 2 + s(2 + 1, 5)

Now textually replace all false conditionals with the alternative and all true conditionals with the consequence. We have only false conditionals, so we textually replace that expression with the alternative:

---> 2 + s(2 + 1, 5)

Now, to save me having to type all those + signs, textually replace constant arithmetic with its value. (This is a bit of a cheat, but I don't want to have to keep track of all the parentheses!)

---> 2 + s(3, 5)

Now search-and-replace, this time with the body for the call, 3 for a and 5 for b. We'll put the replacement for the call in parentheses:

---> 2 + (3 > 5 ? 0 : 3 + s(3 + 1, 5))

And now we just keep on doing those same textual substitution steps:

---> 2 + (false ? 0 : 3 + s(3 + 1, 5))  
---> 2 + (3 + s(3 + 1, 5))                
---> 2 + (3 + s(4, 5))                     
---> 2 + (3 + (4 > 5 ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (false ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(5, 5)))
---> 2 + (3 + (4 + (5 > 5 ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (false ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(6, 5))))
---> 2 + (3 + (4 + (5 + (6 > 5 ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + (true ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + 0)))
---> 2 + (3 + (4 + 5))
---> 2 + (3 + 9)
---> 2 + 12
---> 14

All we did here was just straightforward textual substitution. Really I shouldn't have substituted "3" for "2+1" and so on until I had to, but pedagogically it would have gotten hard to read.

Function activation is nothing more than replacing the function call with the body of the call, and replacing the formal parameters with their corresponding arguments. You have to be careful about introducing parentheses intelligently, but aside from that, it's just text replacement.

Of course, most languages do not actually implement activation as text replacement, but logically that's what it is.

So what then is an unbounded recursion? A recursion where the textual substitution doesn't stop! Notice how eventually we got to a step where there was no more s to replace, and we could then just apply the rules for arithmetic.

Answer 4

1.The function is called recursively until a condition is met. That condition is a > b. When this condition is met, return 0. At first glance, I would expect the return value to be 0 which is obviously incorrect.

Here is what the computer computing sumInts(2,5) would think if it were able to:

I want to compute sumInts(2, 5)
for this, I need to compute sumInts(3, 5)
and add 2 to the result.
  I want to compute sumInts(3, 5)
  for this, I need to compute sumInts(4, 5)
  and add 3 to the result.
    I want to compute sumInts(4, 5)
    for this, I need to compute sumInts(5, 5)
    and add 4 to the result.
      I want to compute sumInts(5, 5)
      for this, I need to compute sumInts(6, 5)
      and add 5 to the result.
        I want to compute sumInts(6, 5)
        since 6 > 5, this is zero.
      The computation yielded 0, therefore I shall return 5 = 5 + 0.
    The computation yielded 5, therefore I shall return 9 = 4 + 5.
  The computation yielded 9, therefore I shall return 12 = 3 + 9.
The computation yielded 12, therefore I shall return 14 = 2 + 12.

As you see, some call to the function sumInts actually returns 0 however this not the final value because the computer still has to add 5 to that 0, then 4 to the result, then 3, then 2, as described by the four last sentences of the thoughts of our computer. Note that in the recursion, the computer does not only have to compute the recursive call, it also has to remember what to do with the value returned by the recursive call. There is a special area of computer's memory called the stack where this kind of information is saved, this space is limited and functions that are too recursive can exhaust the stack: this is the stack overflow giving its name to our most loved website.

Your statement seems to make the implicit assumption that the computer forgets what it were at when doing a recursive call, but it does not, this is why your conclusion does not match your observation.

2.Printing out the value of 'a' on each iteration yields a value which I would expect: 2, 3, 4, 5 (at which point 5+1 > b which meets the first condition: a > b) but I still don't see how the value of 14 is achieved.

This is because the return value is not an a itself but the sum of the value of a and the value returned by the recursive call.

Answer 5

To understand recursion you must think of the problem in a different way. Instead of a large logical sequence of steps that makes sense as a whole you instead take a large problem and break up into smaller problems and solve those, once you have an answer for the sub problems you combine the results of the sub problems to make the solution to the bigger problem. Think of you and your friends needing to count the number of marbles in a huge bucket. You do each take a smaller bucket and go count those individually and when you are done you add the totals together.. Well now if each of you find some friend and split the buckets further, then you just need to wait for these other friends to figure out their totals, bring it back to each of you, you add it up. And so on. The special case is when you only get 1 marble to count then you just return it back and say 1. let the other people above you do the adding you are done.

You must remember every time the function calls itself recursively it creates a new context with a subset of the problem, once that part is resolved it gets returned so that the previous iteration can complete.

Let me show you the steps:

sumInts(a: 2, b: 5) will return: 2 + sumInts(a: 3, b: 5)
sumInts(a: 3, b: 5) will return: 3 + sumInts(a: 4, b: 5)
sumInts(a: 4, b: 5) will return: 4 + sumInts(a: 5, b: 5)
sumInts(a: 5, b: 5) will return: 5 + sumInts(a: 6, b: 5)
sumInts(a: 6, b: 5) will return: 0

once sumInts(a: 6, b: 5) has executed, the results can be computed so going back up the chain with the results you get:

 sumInts(a: 6, b: 5) = 0
 sumInts(a: 5, b: 5) = 5 + 0 = 5
 sumInts(a: 4, b: 5) = 4 + 5 = 9
 sumInts(a: 3, b: 5) = 3 + 9 = 12
 sumInts(a: 2, b: 5) = 2 + 12 = 14.

Another way to represent the structure of the recursion:

 sumInts(a: 2, b: 5) = 2 + sumInts(a: 3, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + sumInts(a: 4, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + sumInts(a: 5, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + sumInts(a: 6, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + 0
 sumInts(a: 2, b: 5) = 14 

Answer 6

Recursion started making sense to me when I stopped reading what others say about it or seeing it as something I can avoid and just wrote code. I found a problem with a solution and tried to duplicate the solution without looking. I only looked at the solution when I got helplessly stuck. Then I went back at trying to duplicate it. I did this again on multiple problems until I developed my own understanding and sense of how to identify a recursive problem and solve it. When I got to this level, I started making up problems and solving them. That helped me more. Sometimes, things can only be learned by trying it out on your own and struggling; until you “get it”.