What is recursion? How does it work?
• Recursion is when a function or procedure calls itself.
• Mutual recursion is when two or more functions or
procedures call each other in a cycle.
• A classic example, factorial:
/* Returns n!= 1*2*3...(n-1)*n for n >= 0. */
int factorial(int n) {
if (n < 2) return 1;
else return factorial(n-1) * n;
}
Another classic example
Fibonacci Numbers
/* Returns nth fibonacci number fn for n >= 0:
- fn = fn-1 + fn-2
- Base case f0 = 0 and f1 = 1 */
int fibonacci (int n) {
if (n >= 2) {
return fibonacci(n-1) + fibonacci(n-2);
} else if (n == 1) {
return 1;
} else { /* n == 0 */
return 0;
}
}
NOTE: Fibonacci and not F-iobonacci!
Function calls (a picture approach)
If A calls B calls C calls D:
A B C D
passes program
control (flow)
returns program
control (flow)
Each call of routine Y from line L of routine X:
• suspends execution of caller X at line L
• starts called routine Y at line 1
• returns to caller X line L+1 on exit from called routine Y
Picture approach: Factorial
int factorial(int n) {
if (n < 2) return 1;
else return factorial(n-1) * n;
factorial(3): }
int factorial (3)
int factorial (2)
int factorial (1)
factorial (2)
factorial (1)
2
1
3
Value returned
Implementation of recursive calls
In practice, a recursive call doesn’t make an entire new copy
of a routine. Instead, it:
• Step 1: records the location to which it will return
• Step 2: reenters the new function code at the beginning
• Step 3: allocates memory for the local data for this new
invocation of the function
- For our factorial example, the parameter argument is the
only local variable.
Iteration versus Recursion
Two implementations of factorial:
int fact_re(int n) { int fact_it(int n) {
if (n < 2) { int result = 1;
return 1; int i;
else { for (i = 1; i <= n; ++i) {
return fact_re(n-1) * n; result *= i;
} }
} return result;
}
How many multiplications does each procedure do?
What other operations (total computational cost) does each
procedure do?
Function call overhead
What’s involved when making a function call?
• save caller’s state
• allocate stack space for arguments
• allocate stack space for local variables
• invoke routine
• at exit (return), release resources
• restore caller’s “environment”
• resume execution of caller
Both the recursive and the iterative routines take time which is
proportional to n, but the iterative algorithm will be much
faster in most language implementations. However, the
recursive is usually more efficient to code!
Combinatorial explosion in Fibonacci
fib(5) = fib(4) + fib(3)
= [ fib(3) + fib(2) ] + [ fib(2) + fib(1) ]
= [ [ fib(2) + fib(1) ] + [ fib(1) + fib(0) ] ] +
[ [ fib(1) + fib(0) ] + 1 ]
= [ [ [ fib(1) + fib(0) ] + 1 ] + [ 1 + 0 ] ] +
[[1+0]+1]
=[[[1+0] +1]+[1+0]]+[[1+0]+1]
Notice that fib(3) is expanded twice, and fib(2) is expanded
three times.
Fibonacci by iteration
int fibonacci(int n) {
int fib0 = 0, fib1 = 1, i, temp;
if (n == 0) return fib0;
else if (n == 1) return fib1;
/* After each iteration, fib0 and fib1 are
* the ith and (i-1)st fibonacci numbers
for (i = 2; i <= n; ++i) {
temp = fib1;
fib1 = fib0 + fib1;
fib0 = temp;
}
return fib1;
}
Choosing recursion
In languages not supporting recursion (e.g. Fortran),
recursion can be simulated with the use of a stack. The
‘recursive’ calls are simulated by iteration and “local data” is
kept on the stack.
Most languages that support recursion use a stack implicitly.
This can cause problems in language implementations where
this implicit stack has limited size.
A recursive implementation is justified when:
• it is difficult to write an iterative version, and
• the recursion doesn’t solve the same subproblems
repeatedly (resulting in a combinatorial explosion)
Our next example (Towers of Hanoi) is perfect for recursion.
Towers of Hanoi
Goal: Move disks from peg A to peg C.
Rule: May only move one disk at a time, onto a smaller disk
or an empty peg.
A B C
Some initial steps
A B C
A B C
Breaking the goal into subgoals
A B C
A B C
Implementation of Towers of Hanoi
/*
* Prints sequence of moves to move n disks (n >= 0)
* from peg source to peg dest using peg inter
* as intermediate.
*/
void move(int n, char source, char dest, char inter) {
if (n > 0) {
move(n - 1, source, inter, dest);
printf(“Move disk from peg %c to peg %c\n”,
source, dest);
move(n - 1, inter, dest, source);
} /* Otherwise n == 0, so do nothing */
}
What is the flow of execution for:
char A = ‘A’, B = ‘B’, C = ‘C’;
move(3,A,C,B);
Picturing the function calls
move(3,A,C,B) move(2,A,B,C) move(1,A,C,B)
move(0,A,B,C)
A to C
move(0,B,C,A)
A to B
move(0,C,A,B) move(1,C,B,A)
C to B
move(0,A,B,C)
A to C
move(0,B,C,A) move(2,B,C,A) move(1,B,A,C)
B to A
move(0,C,A,B)
B to C
move(0,A,B,C) move(1,A,C,B)
A to C
move(0,B,C,A)
The moves: A to C, A to B, C to B, A to C, B to A, B to C, A to C.
Tail recursion
A recursive function is called tail recursive if it only calls itself
as a final operation:
void f(int a, int b) {
int c, d;
if (<some_condition>) { /* Not real C */
/* some statements */
f(c, d); /* end with a recursive call */
} else { /* handle base case */ }
}
This can always be written without recursion as follows:
void f(int a, int b) {
int c, d;
while (<some_condition>) { /* Not real C */
/* some statements */
a = c; b = d;
}
/* handle base case */
}
