## Homework

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

## 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)`

. That function will call `f(4)`

. Which will call `f(5)`

. When will it stop?

It won't! 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.

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

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 *1 ^{2} + 2^{2} + 3^{2} + ... + n^{2}*. 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:

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

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`k`

^{2}, 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 carefull 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

- 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:- if
`B = 0`

then the GCD is`A`

- if
`B > 0`

then the GCD is the same as the GCD of`B`

and`A%B`

.

- if
- 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? - 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.