$ mkdir ~/cs170/labs/lab20 $ cd ~/cs170/labs/lab20
A recursive function is simply a function that contains a function call to itself. While some of you may have inadvertently (or purposefully on occasion) written recursive functions, it is likey the case that you haven't seen the true power of recursion. Recursive functions allow us to break a problem into more managable pieces. While it might not always be the most efficient mechanism, it usually results in incredibly pretty code.
Any code that can be written using recursion can be written using loops. However, sometimes it is easier to program an algorithm using recursion. One case when it is easier to program an algorithm recursively is when it is defined recursively. For example, the Fibonacci sequence is a well-known mathematical sequence in which each term is the sum of the two previous terms. Because the Fibonacci sequence is defined recursively, it is natural to write a recursive function to determine the nth number in the sequence.
Create a file fibonacci.cc, and write a
function long fibonacci(long n) in this file. This function
should recursively compute the nth fibonacci number.
If fib(n) is the nth term of the sequence, then the sequence can be
defined as follows:
\[ \begin{eqnarray} fib(0) &=& 0\\ fib(1) &=& 1\\ fib(n) &=& fib(n - 1) + fib(n - 2) \mbox{ for all n greater than 1} \end{eqnarray} \]
cout << fibonacci(0) << endl; // 0 cout << fibonacci(1) << endl; // 1 cout << fibonacci(2) << endl; // 1 cout << fibonacci(3) << endl; // 2 cout << fibonacci(4) << endl; // 3 cout << fibonacci(5) << endl; // 5
One of the oldest algorithms known is the Euclidean algorithm for computing the greatest common denominator of two numbers. GCD is used when simplifying fractions, and sounds like it should be pretty complicated. However, it is one of the most beautiful algorithms in existence.
Create a file called euclidean.cc, and create a function
int gcd(int a, int b) which computes the greatest common common
denominator of the integers a and b. The logical mechanism for this
function would be to check every integer in the range [1, min(a,
b)]. However, there is an elegant recursive definition that can
compute the gcd:
\[ \begin{eqnarray} gcd(a, 0) &=& a \\ gcd(a, b) &=& gcd(b, a \% b) \end{eqnarray} \]
cout << gcd(3, 6) << endl; // 3 cout << gcd(6, 3) << endl; // 3 cout << gcd(1, 9001) << endl; // 1 cout << gcd(36, 84) << endl; // 12
Your base case is that the integer b is 0. In this case, you want to return the value a.
Your recursive case is simply the recursive call with the
value of b for parameter a, and the value a % b
for the parameter b. Don't forget to return this value!
Remember the Fraction class you wrote about six
weeks ago? Well, there are some operations that might produce a
non-simplified fraction. If you were to show this to a
mathematician, you would likely give them an aneurysm. Add the
Euclidean GCD function to your fraction.cc file, and
use the computed GCD to simplify your fractions.
One nice thing about recursive functions is that they can sometimes be more efficient. Last semester, we made you write the power function using a loop. However, this function uses on the order of n multiplications. Using recursion, we can improve things pretty well.
First, download the CompareData.h file into your directory. You will need this file in order to have your functions return more than one value.
In a file called power.cc, create a function
called CompareData power(long x, long y). This function should follow the
following recursive definition for power, which should
perform fewer multiplications:
\[ \begin{eqnarray} x^1 &=& x\\ x^y &=& x ^ {\frac{y}{2}} \times x ^ {\frac{y}{2}} \mbox{ if y is even and greater than 1}\\ x^y &=& x \times x ^ {\frac{y-1}{2}} \times x ^ {\frac{y - 1}{2}} \mbox{ if y is odd and greater than 1} \end{eqnarray}\]
You should also write a function called CompareData loopPower(long x,
long y),
which computes the power using the traditional loop
methodology. For both of these functions, you should return both
the value of the power, and the number of multiplications required
to compute the value. Test both functions, and make sure the
recursive definition performs fewer multiplications.
CompareData recData = power(2, 3);
cout << "(" << recData.value << ", " << recData.multiplications << ")" << endl; // (8, ###)
CompareData loopData = loopPower(2, 3);
cout << "(" << loopData.value << ", " << loopData.multiplications << ")" << endl; // (8, 2)
loopData = loopPower(2, 10);
cout << "(" << loopData.value << ", " << loopData.multiplications << ")" << endl; // (1024, 9)
recData = power(2, 10);
cout << "(" << recData.value << ", " << recData.multiplications << ")" << endl; // (1024, ###)
recData = power(9, 15);
cout << "(" << recData.value << ", " << recData.multiplications << ")" << endl; // (205891132094649, ###)
loopData = loopPower(9, 15);
cout << "(" << loopData.value << ", " << loopData.multiplications << ")" << endl; // (205891132094649, 14)
Example censored to not spoil the surprise!
Notice in the above recursive definition that while there are really two recursive calls to power, you only really need to perform one in each recursive case. You can store that value in a variable, and use that variable in your multiplications.