Recursion
In this section, we study recursion.
Concept
Recursion is a very powerful problem solving technique.It is the process of defining something in terms of itself.
A recursive function/method is a function that calls itself either directly or indirectly through another function.
We know that the function is to solve a problem. The recursive function knows
how to solve only the simplest case(s) - base case(s).
If the function is called with a base case, the function simply returns the result.
If the function is called with a more complex problem, the function divides the problem into two conceptual pieces:
The function calls a fresh copy of itself to work on smaller problem.
Eventually the function reaches the base.
This is called divide and conquer.
If the function is called with a base case, the function simply returns the result.
If the function is called with a more complex problem, the function divides the problem into two conceptual pieces:
1) A piece that the function knows how to solve;
2) A piece must resemble the original problem, but slightly simpler or smaller version of original problem.
2) A piece must resemble the original problem, but slightly simpler or smaller version of original problem.
The function calls a fresh copy of itself to work on smaller problem.
Eventually the function reaches the base.
This is called divide and conquer.
Linear Recursion Example: Factorial
The linear recursion makes at most one recursive call each time it is invoked.n! = n * (n-1) * ( n-2) …… 1
0! = 1
1! = 1
5! = 5*4*3*2*1
Iterative Solution:
f = 1;
for (int i = 5; i>=1; i--)
f *= i;
for (int i = 5; i>=1; i--)
f *= i;
Recursion Analysis with Recursion Trace:
n! = n * (n-1)!
5! = 5 * (4*3*2*1)
5! = 5*4!
4! = 4*3!
3! = 3*2!
2! = 2*1!
1! = 1 (base case)
Binary Recursion Example: Fibonacci Series
The binary recursion makes two recursive calls each time it is invoked.0, 1, 1, 2, 3, 5, 8, 13, 21, ……
| Position/Index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ... |
| Fibonacci Number: | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | ... |
Iterative Solution:
Recursion Analysis with Recursion Trace:
fib(0) = 0
fib(1) =1
fib(n) = fib(n-1) + fib(n-2)
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
......
Important Notes
Any problem that can be solved recursively can also be solved iteratively, with a loop.Some challenge repetitive problems are more easily solved with recursion than with iteration.
However, in many cases, recursive algorithms are less efficient than iterative algorithms.
Recursive solutions repetitively:
allocate memory for parameters and local variables,
store the address of where control returns after the method terminates.
store the address of where control returns after the method terminates.
These actions are called overhead and take place with each method call.
This overhead does not occur with a loop.
This overhead does not occur with a loop.