C C++ Java Data Structure Python JavaScript CSS Ajax PL/SQL PHP Puzzles C programs C++ programs Java programs

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:

  1. Direct recursion
  2. 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:

  1. Linear recursion
  2. Binary recursion
  3. 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:

  1. 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.
  2. 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.








COMMENTS