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

We already had a "sneak peek" at recursion in a previous lecture. 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). To do this, we consider a concrete example: a recursive function for computing the factorial of a number. 
int factorial(int n)
{
  if (n == 1)
    return 1;
  else
    return n * factorial(n-1);
}
 
int main()
{
  int k = 4;
  int f = factorial(4);
  cout << f << endl;
  return 0;
}
Your instructor will have gone through a nice demo using main and factorial. The key take-away from this is that there is not contradiction in having multiple active calls to a function (like factorial) because each function call is essentially its own copy of the function. So we end up with a "stack" of function calls that includes many copies of the factorial function, but they're all called with different argument values.


http://xkcd.com/244/

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

Last class we saw some examples of recursive functions, i.e. functions whose definitions included calling themselves. This may sound a little strange, but makes sense as you step through such a function using the debugger. 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 to ... f(3) f(4) f(5) f(6)
awaiting return ... main() f(3)
main() 		f(4)
f(3)
main() 		f(5)
f(4)
f(3)
main()
You can see that the stack of functions awaiting the return of the most recently called function simpy 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. A proper recursive function must always have a base case, meaning a way to return without making a recursive call, which is the mechanism that stops this process of ever more recusive calls and an ever growing stack of function calls waiting on the return of other function calls. Moreover, this base case, i.e. this way of returning without making a recursive call, must be something which we'll eventually hit. Once we hit it, we can start taking function calls off the top of the stack and returning from them.

Note: If you run a program with an infinite recursion, you end up with a segfault. This is because the stack of function call records ("the stack") keeps growing until we run out of space. We can see this with valgrind:

foo.cpp compiling and running 
int f(int k)
{
  int a = k*k;
  int b = f(k + 1);
  return a + b;
}

int main() {
  f(5);
  return 0;
}
 
$ g++ foo.cpp -o foo
$ valgrind ./foo
==1520653== Memcheck, a memory error detector
==1520653== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==1520653== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==1520653== Command: ./foo
==1520653== 
==1520653== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==1520653== 
==1520653== Process terminating with default action of signal 11 (SIGSEGV)
See where it says "Stack overflow"? That means there were so many recursive calls that we ran out of space for the call stack.

Base Cases

Whether or not we are in the base case is determined by the parameters we're passed. Consider this function 
int sum(int k)
{
  int p = 0, ans = 0;

  // Base case
  if (k == 0)
    return 0;

  // Recursive case
  p = sum(k-1);
  ans = p + k;

  return ans;
}
The base case here is reached when k is zero. Moreover, 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. If we call sum(3) from the main function, the following table shows how the computation evolves over time:
call to/return value sum(3) sum(2) sum(1) sum(0) returns 0 returns 1 returns 3 returns 6
awaiting return ... main() sum(3)
main()		 sum(2)
sum(3)
main()		 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.

Solving problems recursively

We'll talk about a methodology for writing recursive functions. We'll illustrate it as we go along with the folowing problem: Write a function that takes a positive integer n as input and returns the value of 12 + 22 + 32 + ... + n2 . Not a very interesting problem, but so simple that we can concentrate on problem solving 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. 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. 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!
    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). 
    12 + 22 + ... + (k-1)2 + k2
\___________________/
   sumsquare(k-1)
    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;
  }

The key to design functions with recursion the "right way" is not to imagine the call stack and what all those recursive calls are going to look like. Instead, you assume that the recursive call works properly, and make sure that you use the result of the recursive call properly to get the right answer. We can just press the "I believe" button and assume the recursive call will work as long as:

  1. there is a base case, and
  2. every recursive call gets you closer to the base case.

Problems

  1. 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?)
  2. Making Change My solution prints out the coins in decreasing value. Any thoughts on how you could modify it to print out coins in increasing value?
  3. Factorization ... Again. Using the function int firstfactor(int); that you guys defined for me in Class 15 homework, write a recursive function void factor(int n, ostream& OUT); that prints out the factorization of n to the output stream OUT. What's the base case? How could a recursive call call to factor with a smaller n-value help solve the problem? Take a look at my solution.