Recursion

[Dani]

Recursion
Recursive functions are, interestingly enough, functions which call themselves. Instead of performing calculations by calling other functions, they call themselves by passing in different parameters each time. This forms an almost loop-like effect, where each time a simpler calculation is performed by the function. This is repetitively done until a base-case is met.

Recursive algorithms are not simple and their execution takes up a large amount of space in memory. For this reason, iterative (start to finish, streamlined) algorithms are much more desirable than their recursive counterparts. Although recursion should generally be avoided, there are still algorithms which can only be solved with its use. For such a reason, it is important to study recursion.

The following is the simplest form of a recursive function:

int number()
{

return number();

}

Notice that the function tries to return a value, but to return that value, it must call the function over again. This will result in an increasing stack in memory. Unlike an infinite loop, however, this function will not execute forever. Rather, it will execute until too many calls have been made not getting anywhere. At such a time, it will automatically exit by itself.

Recursive Counters

int count(int x);

int main()
{
int x = 5;
cout << count(x);
return 0;
}

int count(int x)
{
if (x == 0)
return 0;
else
{
cout << x;
return count(x - 1);
}
}
The above is an example program (consisting of a main function and a count function) which counts back from 5 to 0. It operates recursively, as the count function calls itself. Below is a step-by-step procedure of how the recursive stack builds up, and then how it eventually executes itself back down to determine an answer:

the variable x is declared as 5
x is passed into the count function

x is not equal to 0, so the else statement is executed

the value of x, 5, is printed out
the count function returns count(5-1) or count(4)
we don't know the value of count(4), so we must figure it out

the variable x with value 4 is passed into the count function

the procedure above is repeated
the value of x, 4, is printed out
we don't know the value of count(3), so we must figure it out

the procedure above is repeated until x is equal to 1
1 is printed out
we don't know the value of count(0), so we must figure it out
the variable x with value 0 is passed into the count function
it is true that x is equal to 0, so the function returns a 0

Now that we know that the value of count(0) = 0, we can deduce the value of count(1), which we said was equal to count(0). Thus, count(2), count(3), count(4), and count(5) all return 0 as integers. However, the function has been constructed in such a way that it prints out the value of x, resulting in 543210 being printed to the screen.

[wbk]

recursive programming is an important and powerful paradigm. if you want to get into it and be able to "think recursively," you should really spend some time using LISP.

here's a couple of recursive functions that might actually be useful. don't use them in production code if your compiler doesn't support tail call optimization:

/* multiplies x by y */
int multiply(int x, int y)
{
        return (y ? x + multiply(x, y - 1) : 0);
}

/* raises x to the power of y */
int power(int x, int y)
{
        return (y ? x * power(x, y - 1) : 1);
}