Home »
Data Structure
Types of Recursion
Learn: In this article we are going to study about the different types of recursion. What is Indirect recursion? What is direct recursion? What is Linear recursion? What is Binary recursion? What is Multiple recursion?
Submitted by Amit Shukla, on September 30, 2017
Recursion are mainly of two types depending on weather a function calls itself from within itself weather two function call one another mutually. The former is called direct recursion and t latter is called indirect recursion. Thus, the two types of recursion are:
- Direct recursion
- Indirect recursion
Both types of recursion are shown diagrammatically below:
Now before we proceed into the core programming with recursion, first of all we will see a brief idea of storage classes, after which we study some necessary conditions for the recursion to be implemented correctly.
Recursion may be further categorized as:
- Linear recursion
- Binary recursion
- Multiple recursion
1. Linear recursion
In linear recursion the algorithm begins by testing set of base cases there should be at least one. Every possible chain of recursive calls must eventually reach base case, and the handling of each base case should not use recursion. In linear recursion we follow:
- Perform a single recursive call. In this process the recursive step involves a test which decide out of all the several possible recursive calls which one is make, but it should ultimately choose to make just one of these calls each time we perform this step.
- Define each possible recursive call, so that it makes progress towards a base case.
A simple example of linear recursion.
Input
An integer array A and an integer n=1, such that A has at least n elements.
Output
The sum of first n integer in A
If n=1 then
return A[0]
else
return LinearSum (A, n-1) + A[n-1]
In creating recursive methods, it is important to define the methods in a way that facilitate recursion. This sometimes requires we define additional parameters that are passed to the method. For example, we define the array reversal method as ReverseArray (A, i, j), not ReverseArray (A).
Algorithm
ReverseArray (A, i, j);
Input
An array A and non-negative integer indices i and j.
Output
The revesal of the elements in A starting at index I and ending at index j.
If i<j then
Swap A[i] and A[j]
ReverseArray (A, i+1, j-1)
return
2. Binary recursion
Binary recursion occurs whenever there are two recursive calls for each non base case. Example is the problem to add all the numbers in an integer array A.
Algorithm
BinarySum (A, i, n)
Input
An array A and integers i and n.
Output
The sum of the integers in A starting from index i,
If n=1 then
return A[i]
else
return BinarySum [A, i, n/2] + BinarySum [A, i+n/2, n/2]
Example trace
Another example of binary recursion is computing Fibonacci numbers, Fibonacci numbers are defined recursively:
F0 = 0
F1 = 0
Fi = Fi-1 + Fi-2 for i>1
We represent this recursive algorithm as
Algorithm
BinaryFib (K)
Input
Non negative integer K
Output
The Kth Fibonacci number Fk
If K=1
Then return K
Else
return BinaryFib (K-1) + BinaryFib (K-2)
Analyzing the binary recursion Fibonacci algorithm:
Let nk denote number of recursive calls made by BinaryFib (K), then
n0 = 1
n1 = 1
n2 = n1 + n0 + 1 = 1 + 1 + 1 = 3
n3 = n1 + n2 + 1 = 3 + 1 + 1 = 5
n4 = n3 + n2 + 1 = 5 + 3 + 1 = 9
n5 = n4 + n3 + 1 = 9 + 5 + 1 = 15
n6 = n5 + n4 + 1 = 15 + 9 + 1 = 25
n7 = n6 + n5 + 1 = 25 + 15 + 1 = 41
n8 = n7 + n6 + 1 = 41 + 25 + 1 = 67
Note that the value at least doubles for every other value of nk. That is nk > 2k/2. It is exponential.
We can write the better Fibonacci algorithm which can run in O(k) time using linear recursion rather than binary recursion.
3. Multiple Recursion
In multiple recursion we make not just one or two calls but many recursive calls. One of the motivating examples is summation puzzles.
Pot + pan = bib
Dog + cat = pig
Boy + girl = baby
To solve such a puzzle, we need to assign a unique digit (that is 0, 1, 2,…..9) too each letter in the equation, in order to make the equation true. Typically, we solve such a puzzle by using out human observation of the particular we are trying to solve to eliminate configurations (that is, possible partial assignment of digit to letters) until we can work through the feasible configurations left, testing for the correctness of each one.
Algorithm
PuzzleSolve (K, S, U)
Input
An integer K, sequence S and set U (the universe of element to test)
Output
An enumeration of all K length extensions to S using elements in U without repetitions for all e in U.
Remove e from U {e is now being used}
Add e to the end of S
If k=1 then
Test weather S is a configuration that solve puzzle
If S solves puzzle then
Return “solution found;” S
Else
PuzzleSolve (K-1, S, U)
Add e back to U {e is now unused}
Remove e from the end of S.