SI204

Class 20: Lots of Recursion!

Reading

Section 13.1-13.2 of of Absolute C++

 

Lecture

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

 

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 following problem: Write a function that takes a positive integer n as input and returns the value of 12 + 22 + 32 + ... + n2. This problem is simple enough to allow us to 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.      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;
}

To start thinking of recursion the "right way", we're going to use the debugger to run through sumSquare(10), being careful to step over the recursive call ... because after all we're just going to press the "I believe" button and assume it's going to do what it should. This program should help you do that.

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 alpha and beta ...) are two integers with A >= B >= 0 then the GCD of A and B is given by:

o        if B = 0 then the GCD is A

o        if B > 0 then the GCD is the same as the GCD of B and A%B.

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 16, 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 this solution.


Assoc Prof Christopher Brown

Last modified by LT M. Johnson 10/03/2007 01:57:57 PM