What's Recursion Got to do With Russian Dolls?
Before we get into recursion, have you ever seen a Russian doll?
You open it further...
And once more...
Recursion
The process of solving a problem using Recursion is like opening Russian dolls.
Once you open the biggest doll, a similar doll but a bit smaller in size appears.
The same way, when you try to solve a problem using recursion, when you try to solve a bigger problem, that usually requires you to solve a smaller instance of the same problem.
Let's take a look at some problems that can be solved using Recursion
1. Factorial
2. Determine whether a word is a palindrome
3. Computing powers of a number
4. N-th Fibonacci Number
5. Generating permutations of letters such 'a', 'b', 'c'.
Factorial
# n! = n.(n-1).(n-2)...3.2.1
Or, equivalently:
# n! = n.(n-1)!
If n=0, then declare that n!=1.
Otherwise, n must be positive. Solve the subproblem of computing (n-1)! and multiply this result by n, and declare n! equal to the result of this product.
When we're computing n!, in this way, we call the first case, where we immediately know the answer, the base case, and we call the second case, where we have to compute the same function but on a different value, the recursive case.
Distilling the idea of recursion into two simple rules
1. Each recursive call should be on a smaller instance of the same problem, that is, a smaller subproblem.
2. The recursive calls must eventually reach a base case, which is solved without further recursion.
Determine whether a word is a palindrome
1) If the string is made of no letters or just one letter, then it is a palindrome.
2) Otherwise, compare the first and last letters of the string.
3) If the first and last letters differ, then the string is not a palindrome.
4) Otherwise, the first and last letters are the same. Strip them from the string, and determine whether the string that remains is a palindrome. Take the answer for this smaller string and use it as the answer for the original string.
Computing powers of a number
x**n = x**(n-1) * x
N-th Fibonacci Number
fib(n) = fib(n-1) + fib(n-2)
Generating permutations of letters such 'a', 'b', 'c'
Permutations of a, b, c =
a + Permutations of (b, c),
b + Permutations of (a, c), and
c + Permutations of (a, b)
No comments:
Post a Comment