Recursion
Recursive procedures are functions that invoke themselves either
directly (call themselves from within themselves) or
indirectly (calls another method that calls original method.)
Recursion:
. An alternative to iteration
. Recursion can be very elegant at times,
. Not inexpensive to implement...
Classic examples of recursion
. Recursive calculation of a string length, factorials, divide and
conquer, towers of Hanoi, binary searches, and more
Recursive functions are used in many applied areas.
. In artificial intelligence.
. In searching data structures that are themselves "recursive" in nature, such as
trees.
Factorial (N!)
• N! = (N-1)! * N [for N > 1]
• 1! = 1
• 3!
= 2! * 3
= (1! * 2) * 3
=1*2*3
• Recursive design:
• Decomposition: (N-1)!
• Composition: * N
• Base case: 1!
factorial Method
int factorial(int n)
{
int fact;
if (n > 1) // recursive case (decomposition)
fact = factorial(n – 1) * n; // composition
else // base case
fact = 1;
return fact;
}
int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
int factorial(int 2)
{
int fact;
if (n > 1)
fact = factorial(1) * 2;
else
fact = 1;
return fact;
}
int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
int factorial(int 2)
{
int fact;
if (n > 1)
fact = factorial(1) * 2;
else
fact = 1;
return fact;
}
int factorial(int 1)
{
int fact;
if (n > 1)
fact = factorial(n - 1) * n;
else
fact = 1;
return fact;
}
int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
int factorial(int 2)
{
int fact;
if (n > 1)
fact = factorial(1) * 2;
else
fact = 1;
return fact;
}
int factorial(int 1)
{
int fact;
if (n > 1)
fact = factorial(n - 1) * n;
else
fact = 1;
return 1;
}
int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
int factorial(int 2)
{
int fact;
if (n > 1)
fact = 1 * 2;
else
fact = 1;
return fact;
}
int factorial(int 1)
{
int fact;
if (n > 1)
fact = factorial(n - 1) * n;
else
fact = 1;
return 1;
}
int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
int factorial(int 2)
{
int fact;
if (n > 1)
fact = 1 * 2;
else
fact = 1;
return 2;
}
int factorial(int 3)
{
int fact;
if (n > 1)
fact = 2 * 3;
else
fact = 1;
return fact;
}
int factorial(int 2)
{
int fact;
if (n > 1)
fact = 1 * 2;
else
fact = 1;
return 2;
}
int factorial(int 3)
{
int fact;
if (n > 1)
fact = 2 * 3;
else
fact = 1;
return 6;
}
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(decomposition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)
factorial(3) 4
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(decomposition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)
factorial(3) 4
factorial(2) 3
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(decomposition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)
factorial(3) 4
factorial(2) 3
factorial(1) 2
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(composition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)
*
factorial(3) 4
*
factorial(2) 3
*
factorial(1)->1 2
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(composition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)
*
factorial(3) 4
*
factorial(2)->2 3
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(composition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)
*
factorial(3)->6 4
int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
(composition) fact = factorial(n – 1) * n; (composition)
else // base case
fact = 1;
return fact;
}
factorial(4)->24
Anatomy of a Recursive Call
factorial(3) factorial(2) factorial(1)
n=1
f3() ret = 1 * f4
n=2 n=2
f2() ret = 2 * f3 f2() ret = 2 * f3
n=3 n=3 n=3
f1() ret = 3 * f2 f1() ret = 3 * f2 f1() ret = 3 * f2
main() f = main() f= main() f= main() f=
factorial(0)
return return return
n=0
f3() ret = 1
n=1 n=1
f3() ret = 1 * f3() ret = 1 * 1
n=2 n=2 n=2
f2() ret = 2 * f2() ret = 2 * f3 f2() ret = 2 * 1
n=3 n=3 n=3 n=3
f1() f1() f1() f1() ret = 3 * 2
ret = 3 * ret = 3 * f2 ret = 3 * f2
main() f= main() f= main() f= main() f=
Fibonacci Numbers
• The Nth Fibonacci number is the sum of the previous two Fibonacci
numbers
• 0, 1, 1, 2, 3, 5, 8, 13, …
• Recursive Design:
• Decomposition & Composition
• fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
• Base case:
• fibonacci(1) = 0
• fibonacci(2) = 1
fibonacci Method
int fibonacci(int n)
{
int fib;
if (n > 2)
fib = fibonacci(n-1) + fibonacci(n-2);
else if (n == 2)
fib = 1;
else
fib = 0;
return fib;
}
Execution Trace (decomposition)
fibonacci(4)
fibonacci(3) fibonacci(2)
Execution Trace (decomposition)
fibonacci(4)
fibonacci(3) fibonacci(2)
fibonacci(2) fibonacci(1)
Execution Trace (composition)
fibonacci(4)
+
fibonacci(3) fibonacci(2)
+
fibonacci(2)->1 fibonacci(1)->0
Execution Trace (composition)
fibonacci(4)
+
fibonacci(3)->1 fibonacci(2)->1
Execution Trace (composition)
fibonacci(4)->2
Remember:
Key to Successful Recursion
• if-else statement (or some other branching
statement)
• Some branches: recursive call
• "smaller" arguments or solve "smaller" versions of
the same task (decomposition)
• Combine the results (composition) [if necessary]
• Other branches: no recursive calls
• stopping cases or base cases
Tower of Hanoi
• There are three towers
• N-disks, with decreasing sizes, placed on the first tower
• You need to move all of the disks from the first tower to the last
tower
• Larger disks can not be placed on top of smaller disks
• The third tower can be used to temporarily hold disks
Recursive Solution
Recursive Solution
Recursive Solution
Recursive Solution
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Recursive Algorithm
void Hanoi(int n, char a, char b, char c)
{
if (n == 1) /* base case */
printf(“\n Move disk 1 from %c to %c tower”,a,b);
else { /* recursion */
Hanoi(n-1,a,c,b);
printf(“\n Move top disk from %c to %c tower”,a,b);
Hanoi(n-1,c,b,a);
}
}