📘 Module 4: Recursion (5 Lectures)
🎓 Module 4: Recursion
Total Lectures: 5
📖 Lecture 1: Introduction to Recursion
<div style="background:#E3F2FD;padding:15px;border-left:8px solid #1976D2;border-radius:8px;">🔹 What is Recursion?
Recursion is a programming technique in which a function calls itself to solve a problem.
Instead of using loops (for, while), recursion repeatedly breaks a problem into smaller subproblems until a stopping condition (called the Base Case) is reached.
🎯 Real-Life Examples
📂 Opening a folder inside another folder.
🪞 Looking into two mirrors facing each other.
🪆 Russian Dolls (Matryoshka Dolls)
🏢 Climbing stairs one step at a time.
General Syntax
return_type function_name(parameters)
{
if(base_condition)
return value;
return function_name(smaller_problem);
}
Basic Structure of Recursion
Function Call
│
Is Base Case True?
/ \
Yes No
│ │
Return Result Call Same Function
│
Smaller Problem
Important Terms
| Term | Meaning |
|---|---|
| Recursive Function | Function that calls itself |
| Base Case | Stops recursion |
| Recursive Call | Function calling itself |
| Call Stack | Stores function calls |
Example 1: Print Numbers from 1 to 5
#include<stdio.h>
void print(int n)
{
if(n>5)
return;
printf("%d ",n);
print(n+1);
}
int main()
{
print(1);
return 0;
}
Output
1 2 3 4 5
Example 2: Countdown
#include<stdio.h>
void countdown(int n)
{
if(n==0)
return;
printf("%d ",n);
countdown(n-1);
}
int main()
{
countdown(5);
}
Output
5 4 3 2 1
📖 Lecture 2: Developing Recursive Definition of Simple Problems
Steps to Develop Recursive Solution
<div style="background:#FFF3E0;padding:15px;border-left:8px solid orange;border-radius:8px;">Step 1
Identify the smallest problem.
Step 2
Find the Base Case.
Step 3
Reduce the problem.
Step 4
Call the function again.
</div>Example 1: Factorial
Mathematical Definition
5! = 5×4×3×2×1
n! = n × (n-1)!
0! = 1
Algorithm
factorial(n)
if n==0
return 1
return n * factorial(n-1)
Program
#include<stdio.h>
int factorial(int n)
{
if(n==0)
return 1;
return n*factorial(n-1);
}
int main()
{
printf("%d",factorial(5));
}
Output
120
Example 2: Sum of First N Numbers
Sum(5)
5+4+3+2+1
=5+Sum(4)
Program
#include<stdio.h>
int sum(int n)
{
if(n==0)
return 0;
return n+sum(n-1);
}
int main()
{
printf("%d",sum(5));
}
Output
15
Example 3: Power
2^5
=2 × Power(2,4)
Program
#include<stdio.h>
int power(int a,int b)
{
if(b==0)
return 1;
return a*power(a,b-1);
}
int main()
{
printf("%d",power(2,5));
}
Output
32
📖 Lecture 3: Advantages and Limitations of Recursion
🌟 Advantages
<div style="background:#E8F5E9;padding:15px;border-left:8px solid green;border-radius:8px;">✔ Simple Code
✔ Easy to Understand
✔ Less Coding
✔ Suitable for Tree Problems
✔ Useful in Graph Algorithms
✔ Natural Solution for Divide & Conquer
✔ Cleaner than loops in many algorithms
</div>Applications
| Application | Example |
|---|---|
| Tree Traversal | Inorder, Preorder |
| Graph Search | DFS |
| Sorting | Merge Sort |
| Searching | Binary Search |
| Mathematics | Factorial |
| Dynamic Programming | Memoization |
| Compiler | Parsing |
⚠ Limitations
<div style="background:#FFEBEE;padding:15px;border-left:8px solid red;border-radius:8px;">❌ More Memory
❌ Function Call Overhead
❌ Slower than Loops
❌ Stack Overflow
❌ Difficult Debugging
❌ Infinite Recursion if Base Case Missing
</div>Comparison
| Feature | Iteration | Recursion |
|---|---|---|
| Uses Loop | Yes | No |
| Uses Stack | No | Yes |
| Speed | Faster | Slower |
| Memory | Less | More |
| Code | Longer | Shorter |
| Debugging | Easy | Difficult |
📖 Lecture 4: Understanding Internal Stack Implementation
Every Recursive Call Creates
✔ Parameters
✔ Local Variables
✔ Return Address
✔ Function State
All are stored inside the Call Stack.
Example
factorial(4)
Calls
factorial(4)
↓
factorial(3)
↓
factorial(2)
↓
factorial(1)
↓
factorial(0)
Stack Formation
Top
factorial(0)
factorial(1)
factorial(2)
factorial(3)
factorial(4)
Bottom
Returning Phase
factorial(0)=1
↓
factorial(1)=1×1
↓
factorial(2)=2×1
↓
factorial(3)=3×2
↓
factorial(4)=4×6=24
Visual Diagram
CALLS
main()
↓
fact(4)
↓
fact(3)
↓
fact(2)
↓
fact(1)
↓
fact(0)
-------------------
RETURNS
1
↓
1
↓
2
↓
6
↓
24
Stack Memory Illustration
+--------------------+
| factorial(0) |
+--------------------+
| factorial(1) |
+--------------------+
| factorial(2) |
+--------------------+
| factorial(3) |
+--------------------+
| factorial(4) |
+--------------------+
| main() |
+--------------------+
📖 Lecture 5: Programs Using Recursion
Program 1: Fibonacci Series
#include<stdio.h>
int fib(int n)
{
if(n<=1)
return n;
return fib(n-1)+fib(n-2);
}
int main()
{
int i;
for(i=0;i<10;i++)
printf("%d ",fib(i));
}
Output
0 1 1 2 3 5 8 13 21 34
Program 2: Reverse a Number
#include<stdio.h>
void reverse(int n)
{
if(n==0)
return;
printf("%d",n%10);
reverse(n/10);
}
int main()
{
reverse(12345);
}
Output
54321
Program 3: Print Array
#include<stdio.h>
void display(int a[],int n,int i)
{
if(i==n)
return;
printf("%d ",a[i]);
display(a,n,i+1);
}
int main()
{
int a[]={10,20,30,40};
display(a,4,0);
}
Output
10 20 30 40
Program 4: GCD Using Recursion
#include<stdio.h>
int gcd(int a,int b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
int main()
{
printf("%d",gcd(18,12));
}
Output
6
Program 5: Decimal to Binary
#include<stdio.h>
void binary(int n)
{
if(n==0)
return;
binary(n/2);
printf("%d",n%2);
}
int main()
{
binary(13);
}
Output
1101
🎯 Viva Questions
- Define recursion.
- What is a recursive function?
- What is the base case?
- Why is the base case necessary?
- Explain the recursive case.
- What is a call stack?
- Why can recursion cause stack overflow?
- Differentiate recursion and iteration.
- Give real-life examples of recursion.
- Explain internal stack implementation with an example.
📌 Interview Questions
- Can every recursive program be converted into an iterative program?
- Why is recursion slower than iteration?
- What is tail recursion?
- What is indirect recursion?
- How does the compiler manage recursive function calls?
- What happens if the base case is omitted?
- Which data structure is used internally to implement recursion?