Unit II: Recursion

BCSIT-I/II

Compiled By: [Link] Dhaurali

2.1 Introduction to Recursion
The process in which a function calls itself directly or indirectly is called recursion and the
corresponding function is called as recursive function.

Recursion is the technique for defining a problem in terms of one or more smaller versions
of the same problem.

Recursion makes algorithms and its implementation more compact/dense/compressed and

simple.

To solve a problem using recursive method, two conditions must be satisfied.

– Problems could be written or defined in terms of its previous result.

– Problem statement must include a stop condition, otherwise function will

never return.

Example:

Difference between Iteration and Recursion:

2.2 Principle of Recursion
In Data Structures and Algorithms, the principle of recursion states that a problem can be
solved by breaking it into smaller subproblems of the same type, and solving each of
them using the same function.

A recursive solution always depends on two essential components:

1. Recursive Case (Self Call)

• The part where the function calls itself.

• Breaks the problem into a smaller version of the same problem.

• Moves toward the base case.

2. Base Case (Stopping Condition)

• It is the condition under which the recursion stops.

• Prevents infinite function calls.

• Returns a direct result without further recursion.

Without a base case, the program will go into infinite recursion and may cause stack
overflow.

Recursive Program Using Stack:

Recursive functions use something called “the call stack.” When a program calls a function,
that function goes on top of the call stack. Stack is used to keep the successive generations
of local variables, the parameters and the returned values. This stack is maintained by the C
system and lies inside and invisible to the users. Each time that a recursive function is
entered, a new allocation of its variables is pushed on top of the stack. Any reference to a
local variables or parameter is through the current top of the stack. When the function
returns, the stack is popped, the top allocation is freed, and the previous allocation becomes
the current stack top to be used for referencing local variables.

Figure below shows a snapshots of the stack as execution of the fact function proceeds.
Time Complexity: we try to figure out the number of times a recursive
call is being made. If number of times a recursive call is made then the
time complexity of recursive function is Ο (2n) while iterative function
is O (n).

Space Complexity: Space complexity is counted as what amount of

extra space is required for a module to execute. In iterations, the
compiler hardly requires any extra space. The compiler keeps updating
the values of variables used in and space complexity is O (1).

But in recursion, the system needs to store activation record each time a
recursive call is made and space complexity is O (n).

Recursion Tree:

Recursion tree is another method for solving the recurrence relations.

A recursion tree is a tree where each node represents the cost of a

certain recursive sub-problem.

We sum up the values in each node to get the cost of the entire
algorithm.
Eg:

2.3 Types of Recursion

1. Direct Recursion

A recursion in which a function directly calls itself is called Direct Recursion.

Structure:

2. Indirect Recursion

A recursion in which one function calls another function, and that function again calls the
first function, is called Indirect Recursion.

Structure:

3. Linear Recursion

When a recursive function makes only one recursive call each time, it is called Linear
Recursion.

Structure:

4. Tail Recursion

A recursive function in which the recursive call is the last statement executed in the
function is called Tail Recursion.

Structure:
2.4 Recursion Examples
Tower of Hanoi:

It is also called the problem of Benares Temple or Tower of Brahma or Lucas' Tower. The
TOH puzzle was introduced to the west by the French mathematician Edouard Lucas in
1883.

It is a mathematical game or puzzle consisting of three towers (pegs) and a number of disks
of various diameters, which can slide onto any tower.

Rules for TOH:

The objective to move all the disks from the peg A to peg C, using peg B as auxiliary. The
rules to be followed are:

1 Only the top disk on any peg may be moved to any other peg.
2 Only one disk can be moved among the towers at any given time.
3 Larger disk may never rest on a smaller one.

Algorithm for TOH:

To move n disks from A to C, using B as auxiliary:

1 Declare and initialize necessary variables.

• n = number of disks and A, B, C for three pegs being used.
2 If n == 1,
• Move the single disk from A to C and stop.
3 Otherwise
• Move the top n-1 disks from A to B, using C as auxiliary.
• Move the remaining disk from A to C.
• Move the n-1 disks from B to C, using A as auxiliary.
4 Stop
Algorithm for n=3 disks:

1. Move disk 1 from peg A to peg C

2. Move disk 2 from peg A to peg B
3. Move disk 1 from peg C to peg B
4. Move disk 3 from peg A to peg C
5. Move disk 1 from peg B to peg A
6. Move disk 2 from peg B to peg C
7. Move disk 1 from peg A to peg C
Algorithm for n=4 disks:
1. Move disk 1 from peg A to peg B
2. Move disk 2 from peg A to peg C
3. Move disk 1 from peg B to peg C
4. Move disk 3 from peg A to peg B
5. Move disk 1 from peg C to peg A
6. Move disk 2 from peg C to peg B
7. Move disk 1 from peg A to peg B
8. Move disk 4 from peg A to peg C
9. Move disk 1 from peg B to peg C
[Link] disk 2 from peg B to peg A
[Link] disk 1 from peg C to peg A
[Link] disk 3 from peg B to peg C
[Link] disk 1 from peg A to peg B
[Link] disk 2 from peg A to peg C
[Link] disk 1 from peg B to peg C

Recursion Tree for n=4

Fibonacci Series:

Fibonacci series is a series of numbers formed by the addition of the preceding two
numbers in the series. The first two terms are zero and one respectively. The terms after
this are generated by simply adding the previous two terms.

F(n) = F(n-1) + F(n-2) with base cases F(0)=0, F(1)=1

Algorithm Fibonacci(n)

1 Start
2 If n = 0 OR n=1
return n
Else
Return Fibonacci(n-1) + Fibonacci(n-2)
3 Stop
2.5 Applications of Recursion
Recursion is used in:

- Sorting algorithms (Merge Sort, Quick Sort)

- Searching algorithms (Binary Search)

- Tree traversals (inorder, preorder, postorder)

- Mathematical computations (factorial, Fibonacci)

- Backtracking problems
 Assignment-2

1. Define recursion. Explain its basic concept with an example.

2. Explain the principle of recursion with suitable examples.

3. Differentiate between recursion and iteration.

4. Differentiate between linear recursion and tail recursion.

5. Explain the working of recursion using function call stack.

6. Write an algorithm to calculate factorial using recursion.

7. Write a recursive algorithm to generate Fibonacci series.

8. Explain Fibonacci series using recursion with example.

9. Explain Tower of Hanoi problem using recursion.

10. Discuss the advantages and disadvantages of recursion.

11. Explain applications of recursion in computer science.

12. Write short notes on:

• Direct Recursion
• Indirect Recursion
• Linear Recursion
• Tail Recursion