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

Many of the answers above are very good. A useful technique for solving recursion though, is to spell out first what we want to do and code as a human would solve it . In the above case, we want to sum up a sequence of consecutive integers (using the numbers from above):

2, 3, 4, 5  //adding these numbers would sum to 14

Now, note that these lines are confusing (not wrong, but confusing).

if (a > b) {
    return 0 
}

Why the test a>b?, and whyreturn 0

Let's change the code to reflect more closely what a human does

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When 'a equals b' I'm at the most Right integer, return it
  }
  else {
    return a + sumInts(a: a + 1, b: b)
  }
}

Can we do it even more human like? Yes! Usually we sum up from left to right (2+3+...). But the above recursion is summing from right to left (...+4+5). Change the code to reflect it (The - can be a little intimidating, but not much)

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When I'm at the most Left integer, return it
  }
  else {
    return sumInts(a: a, b: b - 1) + b
  }
}

Some may find this function more confusing since we are starting from the 'far' end, but practicing can make it feel natural (and it is another good 'thinking' technique: Trying 'both' sides when solving a recursion). And again, the function reflects what a human (most?) does: Takes the sum of all left integers and adds the 'next' right integer.

Answer 2

A little bit off-topic, I know, but... try looking up recursion in Google... You'll see by example what it means :-)

---

Earlier versions of Google returned the following text (cited from memory):

Recursion

See Recursion

On September 10th 2014, the joke about recursion has been updated:

Recursion

Did you mean: Recursion

---

For another reply, see this answer.

Answer 3

I think the best way to understand recursive functions is realizing that they are made to process recursive data structures. But in your original function sumInts(a: Int, b: Int) that calculates recursively the sum of numbers from a to b, it seems not to be a recursive data structure... Let's try a slightly modified version sumInts(a: Int, n: Int) where n is how many numbers you'll add.

Now, sumInts is recursive over n, a natural number. Still not a recursive data, right? Well, a natural number could be considered a recursive data structre using Peano axioms:

enum Natural = {
    case Zero
    case Successor(Natural)
}

So, 0 = Zero, 1 = Succesor(Zero), 2 = Succesor(Succesor(Zero)), and so on.

Once you have a a recursive data structure, you have the template for the function. For each non recursive case, you can calculate the value directly. For the recursive cases you assume that the recursive function is already working and use it to calculate the case, but deconstructing the argument. In the case of Natural, it means that instead of Succesor(n) we'll use n, or equivalently, instead of n we'll use n - 1.

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        // non recursive case
    } else {
        // recursive case. We use sumInts(..., n - 1)
    }
}

Now the recursive function is simpler to program. First, the base case, n=0. What should we return if we want to add no numbers? The answer is, of course 0.

What about the recursive case? If we want to add n numbers beginning with a and we already have a working sumInts function that works for n-1? Well, we need to add a and then invoke sumInts with a + 1, so we end with:

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        return 0
    } else {
        return a + sumInts(a + 1, n - 1)
    }
}

The nice thing is that now you shouldn't need to think in the low level of recursion. You just need to verify that:

• For the base cases of the recursive data, it calculates the answer without using recursion.
• For the recursive cases of the recursive data, it calculates the answer using recursion over the destructured data.

Answer 4

I think the confusion is stemming from thinking of it as "the same function" being called many times. If you think of it as "many copies of the same function being called", then it may be clearer:

Only one copy of the function ever returns 0, and it's not the first one (it's the last one). So the result of calling the first one is not 0.

For the second bit of confusion, I think it will be easier to spell out the recursion in English. Read this line:

return a + sumInts(a + 1, b: b)

as "return the value of 'a' plus (the return value of another copy of the function, which is the copy's value of 'a' plus (the return value of another copy of the function, which is the second copy's value of 'a' plus (...", with each copy of the function spawning a new copy of itself with a increased by 1, until the a > b condition is met.

By the time you reach the the a > b condition being true, you have a (potentially arbitrarily) long stack of copies of the function all in the middle of being run, all waiting on the result of the next copy to find out what they should add to 'a'.

(edit: also, something to be aware of is that the stack of copies of the function I mention is a real thing that takes up real memory, and will crash your program if it gets too large. The compiler can optimize it out in some cases, but exhausting stack space is a significant and unfortunate limitation of recursive functions in many languages)

Answer 5

I'll give it a go.

Executing the equation a + sumInts(a+1, b), I will show how the final answer is 14.

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

Given: a = 2 and b = 5

1) 2 + sumInts(2+1, 5)

2) sumInts(3, 5) = 12
   i) 3 + sumInts(3+1, 5)
   ii) 4 + sumInts(4+1, 5)
   iii) 5 + sumInts(5+1, 5)
   iv) return 0
   v) return 5 + 0
   vi) return 4 + 5
   vii) return 3 + 9

3) 2 + 12 = 14.

Let us know if you have any further questions.

Here's another example of recursive functions in the following example.

A man has just graduated college.

t is the amount of time in years.

The total actual number of years worked before retiring, can be calculated as follows:

public class DoIReallyWantToKnow 
{
    public int howLongDoIHaveToWork(int currentAge)
    {
      const int DESIRED_RETIREMENT_AGE = 65;
      double collectedMoney = 0.00; //remember, you just graduated college
      double neededMoneyToRetire = 1000000.00

      t = 0;
      return work(t+1);
    }

    public int work(int time)
    {
      collectedMoney = getCollectedMoney();

      if(currentAge >= DESIRED_RETIREMENT_AGE 
          && collectedMoney == neededMoneyToRetire
      {
        return time;
      }

      return work(time + 1);
    }
}

And that should be just enough to depress anyone, lol. ;-P

Answer 6

The way that I usually figure out how a recursive function works is by looking at the base case and working backwards. Here's that technique applied to this function.

First the base case:

sumInts(6, 5) = 0

Then the call just above that in the call stack:

sumInts(5, 5) == 5 + sumInts(6, 5)
sumInts(5, 5) == 5 + 0
sumInts(5, 5) == 5

Then the call just above that in the call stack:

sumInts(4, 5) == 4 + sumInts(5, 5)
sumInts(4, 5) == 4 + 5
sumInts(4, 5) == 9

And so on:

sumInts(3, 5) == 3 + sumInts(4, 5)
sumInts(3, 5) == 3 + 9
sumInts(3, 5) == 12

And so on:

sumInts(2, 5) == 2 + sumInts(3, 5)
sumInts(4, 5) == 2 + 12
sumInts(4, 5) == 14

Notice that we've arrived at our original call to the function sumInts(2, 5) == 14

The order in which these calls are executed:

sumInts(2, 5)
sumInts(3, 5)
sumInts(4, 5)
sumInts(5, 5)
sumInts(6, 5)

The order in which these calls return:

sumInts(6, 5)
sumInts(5, 5)
sumInts(4, 5)
sumInts(3, 5)
sumInts(2, 5)

Note that we came to a conclusion about how the function operates by tracing the calls in the order that they return.