CHAPTER 11

RECURSION
Syllabus
Recursion, Properties of Recursion, Recursive functions: Factorials, Recursive Call stack, The Fibonacci
Sequence, How Recursion Works- The Run Time Stack, Recursive Applications- Recursive Binary Search,
Towers of Hanoi.
Recursion
 A function (or method) can call any other function (or method), including itself.
 A function that calls itself is known as a recursive function.
 Recursion is a technique that solves a problem by solving a smaller
 problem of the same type.
 Types of Recursion
1. Direct Recursion
2. Indirect Recursion
Direct Recursion
The function calls itself repeatedly until a base condition is solved.
Example
def function( )
//…….
function body
……..//
function( ) ---------------Recursive call

Indirect Recursion
The function calls another function which in turn calls the first function.
Example
def function1( )
//…….
function body
……..//
function2( )
def function2( )
//…….
function body
……..//
function1( )
Base Case
 A recursive function definition has one or more base cases (stopping condition), meaning input(s)
for which the function has a ready result without further recurring.
 Because the base case breaks the chain of recursion, it is sometimes also called the "terminating
case".
 For example, for a factorial function the base case can be defined as, factorial (0) = factorial (1) = 1.
Advantages of Recursion

Subject: DSP/20CS41P pg. 1

Recursion leads to solutions that are
1. Compact
2. Simple
3. Easy-to-understand
4. Easy-to-prove-correct
5. Recursion emphasizes thinking about a problem at a high level of abstraction.
Recursive Algorithms Examples
1. Towers of Hanoi
2. Factorial of a Number
3. Fibonacci Sequence
4. Recursive Binary Search
Differences between Recursion and Iteration
RECURSION ITERATION

Terminates when a base case is reached Terminate when a defined condition is met.

Each recursive call requires space in memory Each iteration is not stored in memory

An infinite recursion results in stack overflow An infinite iteration will run while hardware is
error. powered.

Some problems are naturally better suited to Iterative solutions may not always be obvious.
recursive solutions

Properties of a Recursion
All recursive solutions must satisfy three rules or properties:
1. A recursive solution must contain a base case.
2. A recursive solution must contain a recursive case.
3. A recursive solution must make progress toward the base case.
 A recursive solution subdivides a problem into smaller versions of itself.
 For a problem to be subdivided, it typically must consist of a data set or a term that can be divided
into smaller sets or a smaller term.
 This subdivision is handled by the recursive case when the function calls itself.
 The base case is the terminating case and represents the smallest subdivision of the problem.
 It signals the end of the virtual loop or recursive calls.
 Finally, a recursive solution must make progress toward the base case or the recursion will never
stop resulting in an infinite virtual loop.
 This progression typically occurs in each recursive call when the larger problem is divided into
smaller parts.
Recursive Functions:Factorials
The factorial of a positive integer n can be used to calculate the number of permutations of n elements. The

n! = n ∗ (n − 1) ∗(n − 2) ∗ . . . 1
function is defined as:

The factorial function on different integer values:

0! = 1

Subject: DSP/20CS41P pg. 2

1! = 2 ∗ 1
2! = 3 ∗ 2∗ 1
for n > 1, can be rewritten in terms of the previous equation:

1! = 1 ∗ (1 − 1)!
0! = 1

2! = 2 ∗ (2 − 1)!
3! = 3 ∗ (3 − 1)!
4! = 4 ∗ (4 − 1)!
5! = 5 ∗ (5 − 1)!
Since the function is defined in terms of itself and contains a base case, a Recursive definition can be

Below is a simple recursive function to compute the factorial of a number

def factorial(n):
if n==0: ----------- Base case
return 1
return (n*factorial(n-1))
Code:
def factorial(n):
if n==0:
return 1
return (n*factorial(n-1))
num=int(input("Enter a number to find its factorial value "))
print("Factorial of",num,"is: ",factorial(num))
OUTPUT
Enter a number to find its factorial value 4
Factorial of 4 is: 24

Recursive Call Stack

 Recursive functions use something called “the call stack”.
 When a program calls a function, that function goes on top of the call stack.
 Each time when the code calls a function, that function gets added to the stack.
 Once the function ends, it gets taken off the list and the code returns to the calling function.
 Call stack determines the rules for the order that these function call will return,

Subject: DSP/20CS41P pg. 3

The Fibonacci Sequence
 The Fibonacci sequence is a sequence of integer values in which the first two values are both 1 and
each subsequent value is the sum of the two previous values.
 The first 11 terms of the sequence are: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . .
 The nth Fibonacci number can be computed by the recurrence relation (for n > 0):

Below is a simple recursive function to generate Fibonacci sequence of a number

def fib(n):
if (n == 0):
return 0
if n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)

Code:
def fib(n):
if (n == 0):
return 0
if n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
n = int(input("Enter a number"))
print("Fibonacci series of %d numbers are :" % n, end=" ")
for i in range(0, n):

Subject: DSP/20CS41P pg. 4

 print(fib(i), end=" ")

OUTPUT
Enter a number 5
Fibonacci series of 5 numbers are : 0 1 1 2 3

Recursive Applications
Recursive Binary Search
 Binary Search implies continually dividing the searching interval into 2 equal parts to discover an
element in a sorted array, and recurrent binary Search entails breaking down the complete binary
search procedure into smaller issues.
 A recursive binary search is the recursion answer to a binary search.
 The following are the characteristics that all-recursive solutions must meet:
a. A base case is required for a recursive approach.
b. There must be a recursive test case in a recursive approach.
c. A recursive approach has to get nearer to the base case.
 The lowest subdivision of a complicated problem is represented by a base case, which is a final
case.
 So, to perform the binary Search by recursive method, our algorithm must contain a base case and a
recursive case, with the recursive case progressing to the base case.
 Else the process would never finish and result in an endless loop.
 The binary search technique reduces the time it takes to find a specific element inside a sorted
array.
 The binary search method is often implemented iteratively, but we may also implement it
recursively by breaking it down into smaller pieces.
Code:
def binary_search(array, low, high, x):
if high >= low:
mid = (high + low) / 2
if array[mid] == x:
return mid
elif array[mid] > x:
return binary_search(array, low, mid - 1, x)
else:
return binary_search(array, mid + 1, high, x)
else:
return -1
array = [ 2, 4, 6, 8, 20, 40, 60, 80]
x=6
result = binary_search(array, 0, len(array)-1, x)
if result != -1:
print("The index of the Element is", str(result))
else:
print("This element is not present in your Array.")

Subject: DSP/20CS41P pg. 5

Output: The index of element is 2

Tower of Honoi

This is a toy problem that is easily solved recursively. There are three towers (posts) A, B and C. Initially,
there are n disks of varying sizes stacked on tower A, ordered by their size, with the largest disk in the
bottom and the smallest one on top. The object of the game is to have all n discs stacked on tower B in the
same order, with the largest one in the bottom. The third tower is used for temporary storage.

There are two rules:

1. Only one disk may be moved at a time in a restricted manner, from the top of one tower to the top of
another tower. If we think of each tower as a stack, this means the moves are restricted to a pop from one
stack and push onto another stack.
2. A larger disk must never be placed on top of a smaller disk.
Code:
def tower_of_hanoi(disks, source, auxiliary, target):
if(disks == 1):
print('Move disk 1 from rod {} to rod {}.'.format(source, target))
return
tower_of_hanoi(disks - 1, source, target, auxiliary)
print('Move disk {} from rod {} to rod {}.'.format(disks, source, target))
tower_of_hanoi(disks - 1, auxiliary, source, target)
disks = int(input('Enter the number of disks: '))
tower_of_hanoi(disks, 'A', 'B', 'C')
Output:
Enter the number of disks: 3
Move disk 1 from rod A to rod C.
Move disk 2 from rod A to rod B.
Move disk 1 from rod C to rod B.
Move disk 3 from rod A to rod C.
Move disk 1 from rod B to rod A.
Move disk 2 from rod B to rod C.
Move disk 1 from rod A to rod C.
Algorithm
1. Create a Tower of Honoi recursive function and pass two arguments: the number of disks n and the
name of the rods as source, aux and target.
2. The base case is defined when the number of disk is 1.
Simply move one disk from source to destination.
3. Move remaining n-1 disks from source to auxiliary (aux) using target as auxiliary.

Subject: DSP/20CS41P pg. 6

 4. Remaining one disk is moved directly from source to target.
5. Move n-1 disks on the auxiliary to target using source as auxiliary.
QUESTIONS

1. Define Recursion, Direct Recusion, Indirect Recursion

2. Explain types of recursion
3. List the differences between recursion and iteration.
4. List the properties of recursion.
5. Explain recursive binary search with code.
6. Explain the TOH (Tower of Honoi).
7. Explain recursion for factorial of given number- run time stack.
8. Explain recursion for Fibonacci sequence – run time stack.
9. Write the code for a)TOH b)Fibonacci Sequence c)Factorial of given number

Subject: DSP/20CS41P pg. 7