RECURSION
Objectives:
To learn and understand the following concepts:
To design a recursive algorithm
To solve problems using recursion
To understand the relationship and difference between recursion and
iteration
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 2
Session outcome:
At the end of session one will be able to :
• Understand recursion
• Write simple programs using recursive functions
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 3
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.
• A recursive function is a function that invokes / calls itself directly or
indirectly.
• In general, code written recursively is shorter and a bit more elegant,
once you know how to read it.
• It enables you to develop a natural, straightforward, simple solution to a
problem that would otherwise be difficult to solve.
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 4
What is Recursion ?
Mathematical problems that are recursive in nature like factorial,
fibonacci, exponentiation, GCD, Tower of Hanoi, etc. can be easily
implemented using recursion.
Every time when we make a call to a function, a stack frame is
allocated for that function call where all the local variables in the
functions are stored. As recursion makes a function to call itself many
times till the base condition is met, many stack frames are allocated
and it consumes too much main memory and also makes the program
run slower.
We must use recursion only when it is easy and necessary to use,
because it takes more space and time compared to iterative approach.
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 5
Steps to Design a Recursive Algorithm
Base case:
It prevents the recursive algorithm from running forever.
Recursive steps:
Identify the base case for the algorithm.
Call the same function recursively with the parameter having slightly
modified value during each call.
This makes the algorithm move towards the base case and finally
stop the recursion.
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 7
Let us consider the code …
int main() {
int i, n, sum=0;
printf("Enter the limit“);
scanf(“%d”,n);
printf("The sum is %d“,fnSum(n));
return 0; int fnSum(int n){
} int sum=0;
for(i=1;i<=n;i++)
sum=sum+i;
return (sum);
}
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 8
Let us consider same code again …
int main() { int fnSum(int n){
int i, n, sum=0; int sum=0;
printf("Enter the limit“); for(i=1;i<=n;i++)
scanf(“%d”, n);
printf(“The sum is %d“,fnSum(n)); sum=sum+i;
return 0; return (sum);
} }
int fnSum(int x) {
if (x == 1) //base case
return 1;
else
return fnSum(x-1) + x;
//recursive case
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 9
}
Factorial of a natural number–
a classical recursive example
So factorial(5)
= 5* factorial(4)
= 4* factorial(3)
= 3*factorial(2)
= 2* factorial(1)
=
1*factorial(0)
28/07/2025
=1
CSE 1171 Programming for Problem Solving (PPS) - 2024 10
Factorial- recursive procedure
#include <stdio.h>
long factorial (long a) {
if (a ==0) //base case
return (1);
return (a * factorial (a-1)); Output:
} n=5
int main () { 5! = 120
long number;
printf("Please enter the number: “);
scanf(“%d”, &number);
printf(“%ld! = %ld”, number, factorial (number));
return 0;
}
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 11
Recursion - How is it doing!
rFact(5) 12
0
x
5 rFact(4) =2 = 120
4
Notice that the recursion
isn’t finished at the x
bottom -- 4 rFact(3) = = 24
6
It must unwind all the
way back to the top in x =
3 rFact(2) = 6
order to be done.
2
factorial(0) = 1
factorial(n) = n * factorial(n-1) [for n>0] x = 2
2 rFact(1) =
1
long rFact (long a) {
if (a ==0)
return (1); 1
x
rFact(0) = =1
return (a * rFact (a-1)); 1
}
CSE 1171 Programming for Problem Solving (PPS) - 2024 28/07/2025 12
Fibonacci Numbers: Recursion
Fibonacci series is 0,1, 1, 2, 3, 5, 8 …
int rfibo(int n)
{
if (n <= 1) Output:
return n; n=4
else fib = 3
return (rfibo(n-1) + rfibo(n-2));
}
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 14
Recursive Calls initiated by Fib(4)
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 15
Fibonacci Series using Recursion
int rfibo(int);
int main(void){
int n,i, a[20], fibo;
printf("enter any num to n\n“);
scanf(“%d”, n);
printf(“Fibonacci series “);
for (i=1; i<=n; i++) {
fibo = rfibo(i);
printf(“%d”, fibo);
}
return 0;
}
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 16
Factorial- recursive procedure – A
revisit
long factorial (long a) {
if (a ==0) //base case
return (1);
return (a * factorial (a-1)); Output:
} n=5
int main () { 5! = 120
long number;
printf("Please enter the number: “);
scanf(“%d”, &number);
printf(“%ld! = %ld”, number, factorial (number));
return 0;
28/07/2025
} CSE 1171 Programming for Problem Solving (PPS) - 2024 17
Recursion - How is it doing!
rFact(5) 12
0
x
5 rFact(4) =2 = 120
4
Notice that the recursion
isn’t finished at the x
bottom -- 4 rFact(3) = = 24
6
It must unwind all the
way back to the top in x =
3 rFact(2) = 6
order to be done.
2
factorial(0) = 1
factorial(n) = n * factorial(n-1) [for n>0] x = 2
2 rFact(1) =
1
long rFact (long a) {
if (a ==0)
return (1); 1
x
rFact(0) = =1
return (a * rFact (a-1)); 1
}
CSE 1171 Programming for Problem Solving (PPS) - 2024 28/07/2025 18
Static Variable:
The value of static variable persists until the end of the program.
Static variables can be declared as
static int x;
A static variable can be either an internal or external type depending
on the place of declaration.
void fnStat( );
int main() { void fnStat( ){
int i; intx x==0;0;
static int Output:
for( i= 1; i<=3; x = x + 1; x=1
i++) printf(“x=%d”, x=1 2
fnStat( ); x); x=1 3
return 0; }
}
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 19
Reversing a Number
int rev(int num){
#include <stdio.h>
static int n = 0;
int rev(int);
if(num > 0)
int main() {
n = (n* 10) + (num%10) ;
int num;
else
printf(“enter
number)”; return n;
scanf(“%d”,&num); return rev(num/10);
printf(“%d”, }
rev(num)); Output:
return 0; num = 234
} rev = 432
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 20
Sorting a list – Recursive
Base Case:
if length of the list (n) = 1
No sorting, return
Recursive Call:
1. Find the smallest element in the list and place it in
the 0th position
2. Sort the unsorted array from 1.. n-1
sortR(&list[1], n-1)
For eg: list [ ] = {33,-2,0,2,4} n=5
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 21
Sorting a list
list[ ] function calls
{33,-2,0,2,4} sort(list,5) Main()
{-2,33,0,2,4} sort(&list[1],4)
{-2,0,33,2,4} sort(&list[1],3)
{-2,0,2,33,4} sort(&list[1],2)
{-2,0,2,4,33} sort(&list[1],1)
Base case reached .... Return
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 22
Sorting a list
sortR(list, n);// call of fn & display of sorted array in
main()
int sortR(int list[], int ln){ /* move smallest element to 0-th
element */
int i, tmp, min;
if (ln == 1) tmp = list[0];
return 0; list[0] = list[min];
/* find index of smallest no */ list[min] = tmp;
/* recursive call */
min = 0;
for(i = 1; i < ln; i++) return sortR(&list[1], ln-
1);
if (list[i] < list[min])
}
Output:
min = i; Orign. array-: 33 -2 0 2 4
Sorted array -: -2 0 2 4 33
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 23
Recursion - Should I or Shouldn’t I?
• Pros • Cons
– Recursion is a natural fit – Recursive programs typically
for recursive problems use a large amount of
computer memory and the
greater the recursion, the more
memory used
– Recursive programs can be
confusing to develop and
extremely complicated to
debug
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 24
Recursion vs Iteration
RECURSION ITERATION
Uses more storage space Less storage space requirement
requirement
Overhead during runtime Less Overhead during runtime
Runs slower Runs faster
A better choice, a more elegant Less elegant solution for recursive
solution for recursive problems problems
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 25
Recursion – Do’s
• You must include a termination condition or Base
Condition in recursive function; Otherwise your recursive
function will run “forever” or infinite.
• Each successive call to the recursive function must be
nearer to the base condition.
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 26
GCD: Recursion
int gcd(int x, int y)
{
if (y==0) Output:
return (x); x= 24 , y
gcd(24,9) Control In gcd fn on call =9
return gcd(y, x % y); gcd(9,24%9) gcd(9, 6) gcd = 3
} gcd(6,9%6)
gcd(3,6%3)
gcd(6, 3)
gcd(3, 0)
return values return 3
return 3
return 3
return 3
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 28
Summary
• Definition
• Recursive functions
• Problems Solving Using Recursion
• Pros and Cons
• Recursive Vs Iterative Function
28/07/2025 CSE 1171 Programming for Problem Solving (PPS) - 2024 38
