Recursive Algorithms 🌀 🌀 🌀
A recursive algorithm calls a function within its own definition to solve sub-problems of similar nature. Since a recursive
algorithm cannot run indefinitely, it checks for a condition after which it needs to stops calling itself and return.
Consider an example of finding the factorial of a number. Say 5 !
As,
5 ! = 5 * 4 !
4 ! = 4 * 3 !
3 ! = 3 * 2 !
2 ! = 2 * 1 !
1 ! = 1 * 0 !
As we see from above finding 5 ! requires finding 4 ! which further requires finding 3 ! and so on. The sub-problems that find factorials are of similar nature. Once the computation reaches 1 ! the result of 5 ! could be obtained and no further computations would be needed.
Thus the computational problem of finding the factorial of a number can easily be converted into a recursive algorithm as below.
Factorial ( N ) = N * Factorial ( N - 1), with the returning condition of N == 0.
Thus we get the below algorithm
Algorithm Factorial (N)
if N == 0 then
return 1
result = N * Factorial ( N - 1 )
return result
Below are some of the algorithmic problems that make use of recursion.
1. Generating N’th Fibonacci number
2. Generating subsets using recursion
3. Generating permutations using recursion
4. Finding total value of a dollar sack