Lecture notes for March 19, 2003

Recursion part 2

An issue we've been skirting around has been the issue of the fact that there are two major forms of recursion.  For the AP it appears that you will not need to be able to identify which is which, or code them one way or another (at least they won't EXPLICITLY require you to do so), but it is still very very useful for you to know the beast (recursion) as best as you can in order to be as prepared for this exam as you possibly can.  (and you know, for educational reasons as well)

Embedded Recursion:
    Embedded recursion is the form of recursion where the result is embedded within the return statement, and thus you can't figure out what the answer is until the very end when all of the recursive calls are unfolded.  An example of code that works that way is as follows:
(the stupid adder example)
int stupidadd(int a, int b) {
    if (a == 1) return 1 + b;
    else return 1+stupidadd(a-1, b);
}

if we were to run this with an input of 3, 4 the program would first try to figure out what stupidadd (sa for short) (3,4) is

since 3 is not 4, it would say "ah, it's the same as 1+sa(2,4)
the problem is it doesn't know what sa(2,4) is so it holds back the 1, and figures out what sa(2,4) is.  2 is not 1, so it knows that sa(2,4) is the same as 1+sa(1,4), but it doesn't know what sa(1,4) is. So then it realizes that 1 IS the same as 1 (clever, ain't it?) and thus sa(1,4) is 5, once it knows that, it realizes that sa(2,4) is 1+ 5 or 6, and thus sa(3,4) is 1+6 or 7, and thus at the VERY END it can figure out things.  
The point of this is that until the very end, you have no idea what the answer is.  This is probably the purer form of recursion, and it has some advantages, for instance, you can have a recursive step with many calls back to the function in question.  (for instance, return fibonacci(n-1)+fibonacci(n-2))

Tail Recursion:
The other form of Recursion is called Tail recursion.  This is perhaps a little more comfortable for you as it doesn't have the magical step in which you say you want to return the value of the recursive call as the value of the current call.  (return fibonacci(n-1)+fibonacci(n-2) as the return value of fibonacci(n))  Under this form you add an extra argument (which should pretty much ALWAYS be a reference parameter) to help you build up the final result as you go along.  This gives you the advantage of always knowing what the current answer is.  For instance, the above stupidadder would be written as follows as a tail recursive function:
// precondition: result = 0
void stupidadd(int a, int b, int &result) {
    if (a == 1) result += + 1 + b; // yes, this is a violation of how the stupidadder is supposed to work
    else {
    result += 1;
    stupidadd(a-1, b, result);
    }
}

Note: you NEED to manipulate the variable you're using as the reference parameter OUTSIDE of the recursive call.  The reason is that C++ is expecting a variable in its place, NOT an expression.  A-1 is totally fine in that place since a is a normal parameter.

However, there is one sort of catch with embedded recursion: it adds an extra parameter...

Sometimes in life (and on the AP or my classwork) they will demand you write a function that must fit a particular prototype and you realize you can't get your tail recursive (or embedded recursive) function working with only those parameters... but if you had an extra one it would be a cinch.

In those cases, unless told otherwise, you can just write another function!  Let's say for the stupidadder function one were to require you to have it match this format:
int sa(int a, int b);

well you could always write a new function like this:

int sa(int a, int b) {
    int result = 0;
    stupidadder(a, b, result);
}

This new function is called a helper function.  In this case it helps you write the kind of function you want to.  (assuming you prefer tail recursion)

For most cases, you should code whichever you feel more comfortable with.