Introduction to Recursion – Data Structures & Algorithms Lecture Notes

Introduction to Recursion
Data Structures & Algorithms – Lecture Notes
Company: DSA Course | Topic: Recursion




1. Definition of Recursion
Recursion is a technique in which a function calls itself to solve a smaller instance of the same problem.
"A recursive function solves a problem by dividing it into smaller subproblems of the same type."

1.1 Real-Life Understanding
• Looking into two mirrors facing each other
• Russian dolls (Matryoshka) — one doll inside another
• Directory structure in computers (folder inside folder)


2. Basic Structure of Recursion
Every recursive function has two essential components:

Component Description

Base Case Condition where recursion stops; prevents infinite recursion

Recursive Case The function calls itself with a smaller / simpler input


General Form
returnType functionName(parameters) {
if (base_condition) {
return value; // Base case
}
else {
return functionName(smaller_problem); // Recursive call
}
}



3. Recursion Process – How It Works
Recursion operates in two phases:
• Calling Phase (Stack Building): Function calls keep stacking; each call waits for a result.
• Returning Phase (Stack Unwinding): Base case is reached; results return back step-by-step.

Example Trace — Factorial of 4
fact(4)
→ 4 * fact(3)
→ 4 * 3 * fact(2)
→ 4 * 3 * 2 * fact(1)
→ 4 * 3 * 2 * 1
= 24

, 4. Writing Recursive Programs

Steps to Write Recursion
Step Action

1 Identify the base case

2 Break the problem into a smaller subproblem

3 Call the function recursively

4 Combine results

■ Note: Must have a base condition. Problem size must reduce on each call. Avoid infinite recursion.



5. Types of Recursion

5.1 Direct Recursion
Function calls itself directly.
void fun() {
fun();
}



5.2 Indirect Recursion
Function A calls B, which calls A back.
void A() { B(); }
void B() { A(); }



5.3 Tail Recursion
Recursive call is the last operation.
void print(int n) {
if(n == 0) return;
cout << n << " ";
print(n-1);
}


5.4 Non-Tail Recursion
Work is done after the recursive call.
void print(int n) {
if(n == 0) return;
print(n-1);
cout << n << " ";
}



6. Advantages and Disadvantages

■ Advantages ■ Disadvantages

Simple and clean code Uses extra memory (call stack)

Matches mathematical definitions Slower than iterative loops