Data Structures and Algorithms

0404201

5. Recursion
 Preliminaries
The Handshake Problem:
Given that there are n people in a room, each person shakes hands once
with every other person.
What is the total number h(n) of handshakes?

Pattern:
h(4) = h(3) + 3
h(3)=h(2) + 2
h(2) =1
h(1) = 0
h(n) = h(n-1)+n-1
 Introduction
Clarification
Example
h(n) = h(n-1)+n-1 h(5) = h(4)+5-1
h(4) = h(3) + 4-1
Input Simpler Input Operations and Values h(3) = h(2) + 3-1
h(2) = 1
h(1) = 0
Recursive Call
h(n) = h(n-1)+n-1
h(n-1) = h(n-1-1) + n-1-1
h(n-2) = h(n-2-1) + n-2-1
H(5) =4 + 3 +2+1 =10
.
.
h(2) = 1
 Introduction
Definition:
An algorithm which calls itself with smaller (or simpler) input values.

Recursive algorithm produce the output for the current input by

applying some operations to the returned value of calling itself with
smaller (or simpler) input.

When to use Recursion:

If the output for the input x can be obtained by applying simple operation on the
output e.g.: x+/-1,2,3 ….. Recursive Pattern (General Case)
There must be a case where the output is fixed and can be obtained directly.
Base Case

Components of the recursive algorithm: General + Base Case(s)

 Introduction
Need of Recursion:
Recursion is a technique helps to reduce the length of code
and make it easier to read and write.

Recursion is a technique helps to solve problem (task) by

defining it task with its similar subtask.
 Introduction
Properties of Recursion:
• Performing the same operations multiple times with
different inputs.
• In every step, we try smaller inputs to make the problem
smaller.
• Base condition is needed to stop the recursion otherwise
infinite loop will occur.
 Introduction
Recursive Algorithm
– Has one or more base cases and one or more general cases
– Implemented using recursive methods

Recursive method
– Method that calls itself

Base case
– Case in recursive definition in which the solution is obtained directly.
– Stops the recursion

General case
– Case in recursive definition in which a smaller version of itself is called
– Must eventually be reduced to a base case.
 Design
Developing Recursive Algorithm
1. Analyze the problem
2. Find the recursive pattern (General case) and the base case
3. Find the conditions for each alternative in step 2.
4. Combine step 2 and step 3 in conditional (if-else).
5. Besides, step 4 can be implemented using loops

h(n) = h(n-1)+n-1
Recursive Pattern (General Case)
Recursive Call

h(2) = 1 Base Case

 Design (Example 1)
Example (Handshake)
h(2) =1
h(3)=h(2)+2
h(4)=h(3)+3
Analysis
Recursive pattern: H(n)=h(n-1)+n-1
Base case: 1

Algorithm HandShake(n)
1: IF(n==2)
2: return 1
3: Else
4: return Handshake(n-1)+n-1
5: EndIF
End
 Design (Example 2)
Example
f(n) = 1 + 2 + 3 +……..+ n
Analysis
Recursive pattern: f(n) = n + f(n-1)
Base case: 1

Algorithm f(n)
1: IF(n<=1)
2: return 1
3: Else
4: return n + f(n-1)
5: EndIF
End
 Design (Example 3)
Example
Sol(1) =1
Sol(2)=2(Sol(1))+4+2 = 8
Sol(3)=2(Sol(1))+6+2 =10
Sol(4)=2(Sol(2))+8+2 =10

Analysis
Recursive pattern: Sol(n)=2 (Sol(n/2)) + 2n + 2
Base case: 1

Algorithm Sol(n)
1: IF(n==1)
2: return 1
3: Else
4: return 2 * Sol(n/2) +2n +2
5: EndIF
End
 Design (Example 4)
Example
fact(1) =1
fact(2)= 2 * fact (1)
fact(3)= 3 * fact (2)
fact(4)= 4 * fact (3)
fact(5)= 5 * fact (4)
Analysis
Recursive pattern: fact (n) = n*fact(n-1)
Base case: 1

Algorithm fact(int n)
if (n < = 1)
return 1

Else
return n*fact(n-1)
 Design (The Recursive Relation)
The recursive relation development helps in designing the recursive algorithm

A recurrence relation T(n): A recursive function of a variable n, that

represents some recursive algorithm or implemented using recursive algorithm.

A recurrence Components:
–One or more recursive cases
–One or more base cases.

Example of recurrence relations:

 1 n 1  1 n 1, n 2
T (n)  ..... T (n)  .....
2T (n / 2)  2n  2 n  1 T (n  1)  T (n  2) n2
 Design (The Recursive Relation)
For a given recursive relation, the base case and the general case
of its recursive algorithm correspond directly to the base case and
the recursive case of the relation.

Example:
Write the recursive algorithm for the following relation:

Relation Algorithm sol(n)

1: IF (n==1||n==2)
1 n 1, n 2 2: return 1

T (n)  ..... 3: Else
2T (n / 2)  2T (n  1) n  2 4: return
2*sol(n/2) + 2*sol(n-1)
5: EndIF
End
 Design (The Recursive Relation)
Relation Algorithm g(n)
1: IF (n == 1|| n == 2)

 5 n 1, n 2 2:
3:
return 5
ELSE
T (n)  ..... 4: return 3 * g(n-2)
3T (n  2) n2 5:
END
END

Relation Algorithm F(n)

1: IF( n >1)
 5 n 1 2: return F(n-1)+2
T (n)  ..... 3: ELSE
T (n  1)  2 n  1 4: return 5
5: ENDIF
END
 Design (The Recursive Relation)
Algorithm g(n) Relation
1: IF (n == 1)
2: return 2  2 n 1
3: ELSE T (n)  .....
4:
5:
return 3 * g(n /2)+ 5
END
3T (n / 2)  5 n  1
END

Algorithm fib (n) Relation

1: IF( n == 1 || n == 2)
2: return 1  1 n 1,2
3: ELSE T (n)  ...
4: return fib(n–1)+fib(n–2) T (n  1)  T (n  2) n  2
5: ENDIF
END
Memory allocation in Recursion?
How memory is allocated to different function calls in
recursion?
Most compilers implement recursion using stacks
When any function is called from main(), the memory is
allocated to it on the stack.
A recursive function calls itself, the memory for a called function
is allocated on top of the stack (push).
When the base case is reached, the function returns its value to
the function by whom it is called and memory is de-allocated
and the process continues (pop from the stack).

Let us take the example of how recursion works by taking a

simple function.
 Trace and Memory Allocation
factorial(4)
Step 0: executes factorial(4) Stack
Step 9: return 24
Space for Factorial (0)
return 4 * factorial(3)
Space for Factorial (1)
Step 1: executes factorial(3) Space for Factorial (2)
Step 8: return 6
Space for Factorial (3)
return 3 * factorial(2)
Space for Factorial (4)
Step 2: executes factorial(2)
Step 7: return 2 Main Method
return 2 * factorial(1)
Step 3: executes factorial(1)
Step 6: return 1
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1 18
 Trace and Memory Allocation
factorial(4) Stack
Space for Factorial (0)
Step 0: executes factorial(4)
Step 9: return 24 Space for Factorial (1)
return 4 * factorial(3) Space for Factorial (2)
Step 1: executes factorial(3) Space for Factorial (3)
Step 8: return 6
Space for Factorial (4)
return 3 * factorial(2)
Main Method
Step 2: executes factorial(2)
Step 7: return 2
return 2 * factorial(1)
Step 3: executes factorial(1)
Step 6: return 1
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1
Factorial Trace
 Well-Known Problem (Fibonacci)
Fibonacci is an example of binary recursion; where a function
calls itself twice in each run.
 Well-Known Problem (Fibonacci)
1, 1, 2, 3, 5, 8, 13, 21, …..
Example Tracing:
Fibonacci of 1=1,Fibonacci of 2=1 (take n =5)
Fibonacci of 3 = Fibonacci of 1+
Fibonacci 2,
Fibonacci of 4= Fibonacci 3+Fibonacci 2
Analysis
Fibonacci of n= Fibonacci(n-1)+ Fibo (5) = Fibo (4) + Fibo (3)
Fibonacci(n-2)
Recursive pattern: (n-1)+(n-2)
Fibo (4) = Fibo (3) + Fibo (2)
Base case: 1 & 2 Fibo (3) = Fibo (2) + Fibo (1)
Algorithm Fibo(n) Fibo (2) = 1
1: IF(n==1 || n==2) Fibo (1) = 1
2: return 1 ----------------------------
3: Else Fibo (3) = 1+1 = 2
4: return Fibo(n-1)+Fibo(n-2)
5: EndIF Fibo (4) = 2 +1 = 3
End Fact (5) = 3 + 2 = 5
 Recursion vs. Loops
The Factorial Problem
Algorithm Fact(n) Algorithm Fact(n)
1: IF(n==1) 1: results =1
2: return 1 2: For (i:= 1 to n)
3: Else 3: results = results*n
4: return n* Fact(n-1) 4: EndFor
5: EndIF End
End
Algorithm Fact(n)
1: results =1
2: While(n>1)
3: results = results*n
4: n--
5: EndWhile
End
 Recursion vs. Loops

Recursion Iteration
Terminates when the base case Terminates when the condition
becomes true. becomes false.
Used with functions. Used with loops.
Every recursive call needs more
Every iteration does not require
time and extra space in the stack
any extra space.
memory.
Shorter and more elegant code. Larger code size.
 Recursion vs. Loops
Risk:
– Infinite like in loops (iterative solutions)

Algorithm Alg(n) Infinite Loops!

1: i=5 Not Bottoms out (never false condition)
2: While(i>0)
3: …..
4: i++
End

Algorithm Alg(n)
Infinite Loops! 1: For(i:1 to n, i+=2)
For all even numbers (Ex:10) 2: …..
End
 Well-Known Problem (Power)
Power algorithm can be made faster with recursion compared to iterative approach.

Algorithm power (x, n)

1: IF(n == 0)
2: return 1
3: ELSE IF(n == 1)
4: return x
5: ELSE IF ((n % 2) == 0)
6: return power (x,n/2) * power (x, n/2)
7: ELSE
8: return x*power(x,n/2)* power(x, n/2)
9:ENDIF
END
 Real Time Application
• Tree and graph traversing and searching: recursive algorithms can be
used to explore all the nodes or vertices of a tree or graph in a systematic way.

• Sorting algorithms: such as quicksort and merge sort. These algorithms use
recursion to divide the data into smaller subarrays or sublists, sort them, and
then merge them back together.

• Divide-and-conquer algorithms: Many algorithms that use a divide-and-

conquer approach, such as the binary search algorithm, use recursion to break
down the problem into smaller subproblems.

• Backtracking algorithms: to solve problems that involve making a

sequence of decisions, where each decision depends on the previous ones.
These algorithms can be implemented using recursion to explore all possible
paths and backtrack when a solution is not found.