Topics To Cover

Recursive function

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;
}

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 the following program. 


#include <iostream>
using namespace std;

int f(int k);

int main()
{
  cout << f(10) << endl;
  return 0;
}

int f(int k)
{
  int a = k*k;
  int b = f(k + 1);
  return a + b;
}
Let's run the code: 
$ ./a.out
Segmentation fault (core dumped)
[Exit 139 (SEGV)]
The program crashes.

Problem of the above function -- no 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're 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.

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 k as input and returns the value of 12 + 22 + 32 + ... + k2 .

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). 

    sumsquare(1)  : 1*1 
sumsquare(2)  : 1*1 + 2*2
sumsquare(3)  : 1*1 + 2*2 + 3*3
...
sumsquare(k-1): 1*1 + 2*2 + 3*3 + ... + (k-1)*(k-1)
sumsquare(k)  : 1*1 + 2*2 + 3*3 + ... + (k-1)*(k-1) + k*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. (Mandatory) Write a recursive function line. In particular, something like line(10) will print out *'s as shown below. No loops please! 
    
**********
*********
********
*******
******
*****
****
***
**
*
    Take a look at the solution
  2. Revisiting the GCD. 
    
int gcd(int a, int b)
{
  int r;
  while( b != 0 )
  {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
    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.
    Note:
    • A base case is usually related to the stopping condition of a loop.
    • A recursive case is usually related to what is done in the body of a loop.

More recursion examples