Recursive Algorithms ๐ŸŒ€ ๐ŸŒ€ ๐ŸŒ€

Recursion_Factorial 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



Copyright (c) 2019-2022, Algotree.org.
All rights reserved.