Transcript General

Function Recursion Examples
“an example is worth a 1000
lectures”
Three examples:





Factorial function
Iterative version.
Computation of greatest common divisor (Euclidean
Algorithm)
Iterative version
Fibonacci numbers, a cautionary tale, and a fix.
The factorial function
• The factorial function, denoted by n! is defined by:
0! = 1
n! = n (n-1)!
• Example:
– 3! = 3*2! = 3*2*1! = 3*2*1*0! = 3*2*1*1 = 6
• A Recursive C++ function could be:
• int factorial(int n){
if ( n == 0 ) return 1;
return n * factorial(n-1)
}
The factorial function (2)
• Of course, n! is simply the product of all the numbers from 1 to n, so
the following definition could work also:
int factorial1(int n){
product = 1;
for(int i = 1;i<=n;i++){
product *= i;
}
return product;
}
• The recursive definition is more concise; simplicity is in the eye of
the beholder and depends on mindset and experience.
The greatest common divisor (gcd)
The greatest common divisor (gcd) of two numbers m and n is
the biggest number which divides both m and n. There is a nice
method to compute this gcd. Notice that a number k divides m
and n if, and only if it divides n and m remainder n (m % n).
Thus,
gcd(m,n) = gcd(n,m%n)
A few special cases: If m < n, m%n is m so after one step, m is
bigger or equal to n. Thereafter, the numbers decrease; we finish
when the remainder is 0. Here is the function:
int gcd(int m,int n){
if ( n == 0 ) return m;
return gcd(n,m % n);
}
The gcd (2)
Just like with factorial, there is also a version without recursion.
Here is the function:
int gcd(int m,int n){
while ( n > 0 ) {
k = m % n;
m = n;
n = k;
}
return m;
}
Notice the extra variable, since we have to (basically) exchange
the values of m and n.
One more example: a cautionary tale
Another popular example of a recursively defined function is the Fibonacci
mathematical function defined as follows: (called fibo, for short)
fibo(0) = 0
fibo(1) = 1
fibo(n) = fibo(n-1)+fibo(n-2)
(This function is related to rabbit procreation; see the wikipedia for details; it
also has a lot of interesting properties and shows up in nature quite often)
The C++ version looks like this:
int fibo(int n){
if ( n < 2 ) return n;
return fibo(n-1) + fibo(n-2);
}
One more example: a cautionary tale (2)
With an appropriate main driver, lets test this function:
It work fine for small values, but what happens with fibo 45???
(It seems to take a long time: why?)
Let's modify our fbo function so it counts the number of times it has been
called:
int call_count = 0;
int fibo1(int n){
++call_count;
if ( n < 2) return n;
return fibo(n-1) + fibo(n-2);
}
And now, lets run this function:
fibo1(3) = 2 but the call count is 5, fibo1(5) = 5 but the call count is 15!
fibo1(20) is 6765, but the call count is 21891!!! In fact, the call count is
always larger than the value of the function itself (the only exception is
fibo1(1).
One more example: a cautionary tale (3)
Can we define a function that counts the recursive calls of
fibo?
It would be 1 for n < 2, otherwise it would be 1 plus the number
of cals for each of the recursive calls, as in:
int call_count = 0;
int fibo_calls(int n){
++call_count;
if ( n < 2) return 1;
return 1 + fibo_calls(n-1) + fibo_calls(n-2);
}
Since the function structure is the same, the actual count should
be the same as the computed count, and, indeed, it is!
One more example: a cautionary tale (4)
Can we fix it?
The answer is yes, through a process called memoization. To
understand the problem, let us look at the computation of fibo(4):
fibo(4) = fibo(3) + fibo(2) = (fibo(2) +fibo(1)) + (fibo(1) +
fibo(0)) = ((fibo(1) + fibo(0)) + fibo(1)) + (fibo(1) + fibo(0)) = 3
However, we calculated fibo(2) twice, fibo(1) three times and
fibo(0) twice. A lot of extra work! If we store those partial
results, we can avoid the extra work. Where do we store them?
The best possibilities are an array or a vector. we will choose a
vector. The function is on the next slide...
One more example: a cautionary tale (5)
vector <int> fibos;
int fibo(int n){
if ( n < 2) return n;
while ( fibos.size() < n+1 ) fibos.push_back(-1);
if ( fibos[n] > 0 ) return fibos[n];
return fibos[n] = fibo(n-1) + fibo(n-2);
}
Iteratitave fibonacci
Of course, there is also an iterative version:
int it_fibo(int n){
int i,fnm2 = 0,fnm1 =1,fn;
if ( n < 2 ) return n;
for ( i = 2; i <= n; i++){
fn = fnm2 + fnm1;
fnm2 = fnm1;
fnm1 = fn;
}
return fn;
}