# 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:

F_{0}= 0 F_{1}= 0 F_{i}= Fi-1 + Fi-2 for i>1

We represent this recursive algorithm as

**Algorithm**

BinaryFib (K)

**Input**

Non negative integer K

**Output**

The KIf K=1 Then return K Else return BinaryFib (K-1) + BinaryFib (K-2)^{th}Fibonacci number F_{k}Analyzing the binary recursion Fibonacci algorithm:Let n_{k}denote number of recursive calls made by BinaryFib (K), then n_{0}= 1 n_{1}= 1 n_{2}= n1 + n0 + 1 = 1 + 1 + 1 = 3 n_{3}= n1 + n2 + 1 = 3 + 1 + 1 = 5 n_{4}= n3 + n2 + 1 = 5 + 3 + 1 = 9 n_{5}= n4 + n3 + 1 = 9 + 5 + 1 = 15 n_{6}= n5 + n4 + 1 = 15 + 9 + 1 = 25 n_{7}= n6 + n5 + 1 = 25 + 15 + 1 = 41 n_{8}= n7 + n6 + 1 = 41 + 25 + 1 = 67

Note that the value at least doubles for every other value of n_{k}. That is nk > 2^{k/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.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions