DATA STRUCTURES WITH PYTHON CODE:20CS41P
RECURSION
What is Recursion?
Sometimes, the best way to solve a problem is by solving a smaller
version of the exact same problem first.
Recursion is a technique that solves a problem by solving a smaller
problem of the same type.
In computer science, recursion is a method of solving a
computational problem where the solution depends on solutions to
smaller instances of the same problem.
Recursion solves such recursive problems by using functions that
call themselves from within their own code.
The approach can be applied to many types of problems, and
recursion is one of the central ideas of computer science
Recursion in Nature
SEARCH EDUCATIONS Page 1
DATA STRUCTURES WITH PYTHON CODE:20CS41P
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
Recursion leads to solutions that are
1. Compact
2. Simple
3. Easy-to-understand
4. Easy-to-prove-correct
SEARCH EDUCATIONS Page 2
DATA STRUCTURES WITH PYTHON CODE:20CS41P
Recursion emphasizes thinking about a problem at a high level of
abstraction.
Recursive Algorithms Examples
Recursion leads to solutions that are
1. Towers of Hanoi
2. Factorial of a Number
3. Fibonacci Sequence
4. Recursive Binary Search
Run Time Stack: Example Factorial Function: Factorial (3)
Line 1: def fact(n):
Line 2: if n == 1:
Line 3:return n Line 4:
else:
Line 5:return n*fact (n-1)
Recursive Call 1: Initially Value of n = 3
Since the value of n is 3, the control goes to line 5 and the first recursive
call is pushed on to stack with n value = 3
Recursive Call Run Time Stack
def fact() :
if n == 1:
return n
else
return 3 * fact(2)
SEARCH EDUCATIONS Page 3
DATA STRUCTURES WITH PYTHON CODE:20CS41P
Recursive Call 2: Now the value of n = 1
Recursive Call Run Time Stack
def fact() :
if n == 1:
return n
else
return 2 * fact(1)
def fact() :
if n == 1:
return n
else
return 3 * fact(2)
Recursive Call 3: Now the value of n = 1: Base Case is reached
Since the value of n is 1 the base case of this recursion is reached and the
control of the program executes statement @ line 2 and the value 1 is
returned
SEARCH EDUCATIONS Page 4
DATA STRUCTURES WITH PYTHON CODE:20CS41P
SEARCH EDUCATIONS Page 5
DATA STRUCTURES WITH PYTHON CODE:20CS41P
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 base case is required for a recursive approach.
There must be a recursive test case in a recursive approach.
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.
Recursive Binary Search
#In this recursive function base case is element is in the list OR when low
index # crosses high
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)
SEARCH EDUCATIONS Page 6
DATA STRUCTURES WITH PYTHON CODE:20CS41P
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.")
Towers of Hanoi
This is a toy problem that is easily solved recursively.
There are three towers (posts)
𝐴, 𝐵, and 𝐶. 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.
SEARCH EDUCATIONS Page 7
DATA STRUCTURES WITH PYTHON CODE:20CS41P
The third tower is used for temporary storage.
There are two rules:
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.
A larger disk must never be placed on top of a smaller disk.
Towers of Hanoi : Code
# Creating a recursive function
def tower_of_hanoi(disks, source, auxiliary, target):
if(disks == 1):
print('Move disk 1 from pole {} to pole {}.'.format(source, target))
return
# function call itself
tower_of_hanoi(disks - 1, source, target, auxiliary)
print('Move disk {} from pole {} to pole {} .'.format(disks, source, target))
tower_of_hanoi(disks - 1, auxiliary, source, target)
disks = int(input('Enter the number of disks: '))
# We are referring source as A, auxiliary as B, and target as C
tower_of_hanoi(disks, 'A', 'B', 'C') # Calling the function
SEARCH EDUCATIONS Page 8
DATA STRUCTURES WITH PYTHON CODE:20CS41P
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
Direct Indirect
Direct Recursion
The function calls itself repeatedly until a base condition is solved.
Example
def function( )
//……. function body
……..//
function( )
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( )
SEARCH EDUCATIONS Page 9
DATA STRUCTURES WITH PYTHON CODE:20CS41P
The following table outlines the key differences between recursion and
iteration:
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.
SEARCH EDUCATIONS Page 10
DATA STRUCTURES WITH PYTHON CODE:20CS41P
The function is defined as:
n! = n ∗ (n − 1) ∗(n − 2) ∗ . . . 1
The factorial function on different integer values:
0! = 1
1! = 2 ∗ 1
2! = 3 ∗ 2∗ 1
for n > 1, can be rewritten in terms of the previous equation:
0! = 1
1! = 1 ∗ (1 − 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:
return 1
return (n*factorial(n-1))
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
SEARCH EDUCATIONS Page 11
DATA STRUCTURES WITH PYTHON CODE:20CS41P
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):
SEARCH EDUCATIONS Page 12
DATA STRUCTURES WITH PYTHON CODE:20CS41P
return 0
if n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
A function (or method) can call any other function (or method),
including itself. A function that calls itself is known as a recursive
function.
Example
def function( )
//……. function body
……..//
function( ) Recursive call
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 function is defined as:
n! = n ∗ (n − 1) ∗(n − 2) ∗ 1
The factorial function on different integer values: 0! = 1
1! = 2 ∗ 1
2! = 3 ∗ 2∗ 1
for n > 1, can be rewritten in terms of the previous equation:
0! = 1
1! = 1 ∗ (1 − 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
SEARCH EDUCATIONS Page 13
DATA STRUCTURES WITH PYTHON CODE:20CS41P
Below is a simple recursive function to compute the factorial of a number
def factorial(n):
if n==0:
return 1
return (n*factorial(n-1))
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)
Program to demonstrate Recursive operation of Factorial of a number
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))
SEARCH EDUCATIONS Page 14
DATA STRUCTURES WITH PYTHON CODE:20CS41P
OUTPUT
Enter a number to find its factorial value 4 Factorial of 4 is: 24
Program to generate Fibonacci sequence using recursion
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):
print(fib(i), end=" ")
OUTPUT
Enter a number 5
Fibonacci series of 5 numbers are : 0 1 1 2 3
SEARCH EDUCATIONS Page 15
