Table of Contents
show
A function that calls itself is known as a recursive function, and the phenomenon is known as recursion.
Every recursive solution consists of two cases:
Base case
- Base case is the smallest instance of problem which can be solved easily and there is no need to further express the problem in terms of itself, i.e. in this case no recursive call is given and the recursion terminates
- Base case forms the terminating condition of the recursion
- There may be more than one base case in a recursive solution
- Without the base case, the recursion will never terminate and will be known as infinite recursion
Example
n==0 is the base case for factorial of a number
Recursive case
In recursive case, the problem is defined in terms of itself, while reducing the problem size
Example
when fact(n) is expresses as n*fact(n-1), the size of the problem is reduced from n to n-1
fact(n) = 1 when n = 0 fact(n) = n * fact (n-1) when n>0
Advantages
- Easy solution for recursively defined problems
- Complex programs can be easily written in less code
Disadvantages
- Recursive code is difficult to understand and debug
- Terminating condition is must, otherwise it will go in infinite loop
- Execution speed decreases because of function call and return activity many times
- Recursive calls are expensive as they take up lot of memory and time
Views: 0