Recursion that works - how a recursive "factorial" function gets executed

Recursive function: A function is recursive if the function, in order to compute its result, ends up "calling itself".

This idea can seem paradoxical when you're just getting started, so we'll go through an example of how the computer really handles it in order to explain away the paradox. The upshot is that we have the same function, yes, but it is one call of the function that in turn makes a separate call to the same function, but with different arguments.

Example

To do this, we consider a concrete example: a recursive function for computing the factorial of a number. 

int fact(int n)
{
  if (n == 1)
    return 1;
  else
    return n * fact(n-1);
}


int main()
{
  int f = fact(5);
  cout << f << endl;
  return 0;
}
The key take-away from this is that there is not contradiction in having multiple active calls to a function (like fact).

In particular:

  • A function call to fact may in turn make another function call to fact. See the diagram on the left.
  • This means that we will end up with a "stack" of function calls which are many copies of the fact function. See the diagram below:
    ------------------------------- time ------------------------------>
    fact(5)
    main()

    fact(5)
    called     		...
    fact(1)
    fact(2)
    fact(3)
    fact(4)
    fact(5)
    main()

    fact(1)
    called     		...
    fact(2)
    fact(3)
    fact(4)
    fact(5)
    main()

    fact(1)
    returned     		...
    main()

    fact(5)
    returned
  • However, each function call will have a different argument value.

Recursion that doesn't work - the need for a Base Case


http://xkcd.com/244/
Before we start looking at how one devises a recursive function that accomplishes a given task, let's look at a recursive function that doesn't work.

Consider this function: 


int f(int k)
{
  int a = k*k;
  int b = f(k + 1);
  return a + b;
}
Now, let us suppose that we start off by calling f(3). The following table shows what happens as time evolves a few steps:
call f(3) call f(4) call f(5) call f(6)
call stack main() f(3)
main() 		f(4)
f(3)
main() 		f(5)
f(4)
f(3)
main()

Problem of the above function -- infinite recursion

You can see that the stack of functions awaiting the return of the most recently called function simply keeps growing and growing ... and there's nothing there to stop it from growing further! This function has an infinite recursion, meaning that recursive calls are made over and over again, without any mechanism to stop the process.

Fix: Exit strategy -- base case

A proper recursive function must always have a base case:

Base Cases

Whether or not we are in the base case is determined by the parameters we've passed. Consider this function 

int sum(int k)
{
  int p = 0, ans = 0;

  if (k == 0)
    return 0;

  p = sum(k-1);
  ans = p + k;

  return ans;
}
 Q. Specify the base case of this function. 
Answer: When k is zero.
Q. Does every function call eventually hit the base case?

Answer: 


Yes. No matter how big the number in our initial call to sum, we
must eventually reach our base case, because the argument to our recursive
calls keep getting smaller and smaller, until they finally reach zero.
As an example for the second question, if we call sum(3) from the main function, the following table shows how the computation evolves over time:
call sum(3) call sum(2) call sum(1) call sum(0) returns 0 returns 1 returns 3 returns 6
call stack main() sum(3)
main()		 sum(2)
sum(3)
main()		 sum(1)
sum(2)
sum(3)
main()		 sum(0)
sum(1)
sum(2)
sum(3)
main()		 sum(1)
sum(2)
sum(3)
main()		 sum(2)
sum(3)
main()		 sum(3)
main()		 main()
So, to be a properly defined recursive function you must have a base case, i.e. a way for the function to return without making a recursive call, and your recursive calls must work towards the base case.

Q. Does every function call to sum() eventually hit the base case, really?
Answer: Well, not really. For example, sum(-1) has infinite recursion. It never reaches the base case. If we assume that the input to the function is positive, the function works correctly.

Solving problems recursively

We'll talk about a methodology for writing recursive functions. We'll illustrate it as we go along with the following problem:

Write a function that takes a positive integer n as input and returns the value of 12 + 22 + 32 + ... + n2 .

It is a simple problem that we can concentrate on using recursion.

When you're setting out to write a recursive function, you at least have a prototype in mind. In this case that'll be 

int sumsquare(int k);
That part is easy, and no recursion is involved.

Writing recursion: two questions

If we're going to solve this recursively, we have two big questions:

  1. What is the base case?

    In other words, for what inputs can we automatically just spit out the answer without having to do any real work? In particular, without needing a recursive call?

    For this problem, I'm asking what values of k are particularly easy to give the answer to? Of course, since we're assuming that k is positive, the easiest value for k is 1. If k is one we can just immediately return 1. So that gives us our base case. 

    
// Base case
if (k == 1)
  return 1;
  2. What is the recursive case?

    How would the answer to a "smaller" problem of the same kind help get the answer to the original problem. In other words, if I just assume that the function (which I already have the prototype for) just "works" for smaller inputs, how will that help me get the answer?

    For this problem, what I'm asking is this: How would the answer to sumsquare(k-1) help me figure out the answer to sumsquare(k)? Well, all I'd need to add to the result of sumsquare(k-1) is a k2, and I'd have the answer to sumsquare(k). This then gives us our recursive case: 

    
// Recursive case
int p = sumsquare(k - 1);
int ans = p + k*k;
return ans;
If you put the answer to these questions together, you'll have a recursive function that solves the problem. Really the two keys are to find a base case, and to assume your function already works as you go about using recursive calls to define it. In the above we just assumed that sumsquare would work right when we called sumsquare(k - 1). So, here's the complete function: 

int sumsquare(int k)
{
  // Base case
  if (k == 1)
    return 1;

  // Recursive case
  int p = sumsquare(k - 1);
  int ans = p + k*k;
  return ans;
}

Important: Tip on writing a recursive case:

Sometimes it's helpful to think about recursion this way:

If I had a function that solved my problem, but only for arguments of value less than n, how could I solve the problem for n?

For example, suppose I had a function factorialSmall that computed the factorial of its argument, but only for numbers less than 10. How could I use it to solve factorial 10? Easy: 
10*factorialSmall(9)
 Now, suppose factorialSmall worked for any number less than some value n, but I'm not telling you exactly what n is. How could I compute factorial(n)? Easy: 
n*factorialSmall(n-1)

Great! Now I've got my recursive case!

Practice Problems

  1. Write a recursive function line. In particular, something like line(10) will print out *'s as shown below. 
    
**********
*********
********
*******
******
*****
****
***
**
*
    Take a look at the solution
  2. Revisiting the GCD. The way Euclid would've phrased his GCD algorithm would be more like this: If A and B (okay, he was greek, so it probably would've been α and β ...) are two integers with A >= B >= 0 then the GCD of A and B is given by: Using this phrasing of the algorithm, implement the GCD as a recursive function. Here's a solution. (Think, what's the base case? What's the recursive case? Does the recursive case work towards the base case?)

More recursion examples