Ugenz Academy/Tutorial

Recursion

10 min read1,805 words

Reading progress

Keep learning

Recursion

Recursion is a programming technique where a function calls itself to solve a problem by breaking it into smaller versions of the same problem.

The most important idea is:

A recursive function must have a stopping condition called the base case.

1. Simple Example

Let's print numbers from 5 down to 1.

Normal approach

#include <iostream> using namespace std; int main() { for (int i = 5; i >= 1; i--) { cout << i << " "; } return 0; }

Output:

5 4 3 2 1

Now let's do the same using recursion.

Recursive approach

#include <iostream> using namespace std; void countdown(int n) { if (n == 0) { return; // Base case } cout << n << " "; countdown(n - 1); // Recursive call } int main() { countdown(5); return 0; }

Output:

5 4 3 2 1

2. Two Important Parts of Recursion

Every recursive function generally has two parts:

① Base Case

The condition that stops recursion.

if (n == 0) { return; }

② Recursive Case

The function calls itself with a smaller/simpler problem.

countdown(n - 1);

So:

Recursive Function | ├── Base Case → Stop | └── Recursive Case → Call itself

3. How Recursion Works

Consider:

countdown(3);

The function executes:

countdown(3) | └── countdown(2) | └── countdown(1) | └── countdown(0) | └── STOP

The calls happen like this:

countdown(3) countdown(2) countdown(1) countdown(0)

When countdown(0) reaches the base case, the function starts returning.

countdown(0) returns ↓ countdown(1) returns ↓ countdown(2) returns ↓ countdown(3) returns

4. Recursion Uses the Stack

This is very important because we just studied Stack.

When a function is called, information about that function call is stored in the call stack.

For:

countdown(3);

the stack grows:

┌──────────────┐ │ countdown(1) │ ├──────────────┤ │ countdown(2) │ ├──────────────┤ │ countdown(3) │ └──────────────┘

Then when the base case is reached, calls are removed from the stack:

countdown(1) → return countdown(2) → return countdown(3) → return

Key connection

Recursion internally uses the call stack.

That's why recursion is directly related to the Stack topic we just studied.

5. Factorial Using Recursion

Factorial:

5! = 5 × 4 × 3 × 2 × 1

We can define it recursively:

5! = 5 × 4! 4! = 4 × 3! 3! = 3 × 2! 2! = 2 × 1! 1! = 1

C++ code

#include <iostream> using namespace std; int factorial(int n) { if (n == 0 || n == 1) { return 1; // Base case } return n * factorial(n - 1); } int main() { cout << factorial(5); return 0; }

Output:

120

Execution

factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3) = 5 * 4 * 3 * factorial(2) = 5 * 4 * 3 * 2 * factorial(1) = 5 * 4 * 3 * 2 * 1 = 120

6. Recursion Tree for Factorial

For:

factorial(4)

calls go down:

factorial(4) ↓ factorial(3) ↓ factorial(2) ↓ factorial(1) ↓ 1

Then values return upward:

1 ↑ 2 × 1 = 2 ↑ 3 × 2 = 6 ↑ 4 × 6 = 24

Final answer:

24

7. Sum of First N Numbers

Suppose:

1 + 2 + 3 + 4 + 5 = 15

We can define:

sum(n) = n + sum(n-1)

C++ code

int sum(int n) { if (n == 0) { return 0; } return n + sum(n - 1); }

For:

sum(5)

we get:

5 + sum(4) 4 + sum(3) 3 + sum(2) 2 + sum(1) 1 + sum(0)

Then:

sum(0) = 0 sum(1) = 1 sum(2) = 3 sum(3) = 6 sum(4) = 10 sum(5) = 15

8. Print Numbers 1 to N

Earlier we printed:

5 4 3 2 1

We can also print:

1 2 3 4 5

using recursion.

void printNumbers(int n) { if (n == 0) { return; } printNumbers(n - 1); cout << n << " "; }

For:

printNumbers(5);

The calls go down first:

printNumbers(5) ↓ printNumbers(4) ↓ printNumbers(3) ↓ printNumbers(2) ↓ printNumbers(1) ↓ printNumbers(0)

Then printing happens while returning:

1 2 3 4 5

Output:

1 2 3 4 5

This is an important recursion concept:

Code before the recursive call executes while going down; code after the recursive call executes while returning.

9. Reverse a String Using Recursion

Suppose:

"UDAY"

We want:

"YADU"

One approach:

#include <iostream> #include <string> using namespace std; void reverseString(string &s, int left, int right) { if (left >= right) { return; } swap(s[left], s[right]); reverseString(s, left + 1, right - 1); } int main() { string s = "UDAY"; reverseString(s, 0, s.length() - 1); cout << s; return 0; }

Output:

YADU

The idea is:

U D A Y ↑ ↑ swap Y D A U ↑ ↑ swap Y A D U

10. Check Palindrome Using Recursion

A palindrome reads the same forward and backward.

Examples:

MADAM LEVEL RADAR

We compare the first and last characters.

bool isPalindrome(string &s, int left, int right) { if (left >= right) { return true; } if (s[left] != s[right]) { return false; } return isPalindrome(s, left + 1, right - 1); }

For:

MADAM

comparisons:

M == M A == A D

Therefore:

true

11. Fibonacci Using Recursion

Fibonacci sequence:

0 1 1 2 3 5 8 13 21 ...

Definition:

F(n) = F(n-1) + F(n-2)

Base cases:

F(0) = 0 F(1) = 1

C++ code

int fibonacci(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } return fibonacci(n - 1) + fibonacci(n - 2); }

For:

fibonacci(5)

the calls form a tree:

F(5) / \ F(4) F(3) / \ / \ F(3) F(2) F(2) F(1) / \ F(2) F(1)

Notice something important:

The same values are calculated again and again.

That's why this simple recursive Fibonacci implementation is inefficient.

Complexity

Time: O(2^n) Space: O(n)

The space is O(n) because the deepest chain of recursive calls is about n.

Later, Dynamic Programming will teach us how to avoid these repeated calculations.

12. Recursion vs Iteration

Recursion

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }

Iteration

int factorial(int n) { int result = 1; for (int i = 1; i <= n; i++) { result *= i; } return result; }

Both can solve the same problem.

RecursionIteration
Function calls itselfUses loops
Uses call stackUsually less extra memory
Often easier for tree problemsOften simpler for straightforward loops
Can be elegantUsually more memory efficient
Can cause stack overflowUsually avoids recursive stack growth

13. Time and Space Complexity

Consider:

void print(int n) { if (n == 0) return; cout << n << " "; print(n - 1); }

There are n function calls.

Therefore:

Time Complexity = O(n)

And because all recursive calls remain on the call stack until they return:

Space Complexity = O(n)

So:

Time → O(n) Space → O(n)

14. What Happens Without a Base Case?

This is dangerous:

void fun() { cout << "Hello"; fun(); }

There is no stopping condition.

The calls keep increasing:

fun() ↓ fun() ↓ fun() ↓ fun() ↓ fun() ↓ ...

Eventually the call stack becomes full.

This causes:

Stack Overflow

So always ask:

When should my recursion stop?

15. Types of Recursion

Direct Recursion

A function calls itself directly.

void fun() { fun(); }

Indirect Recursion

One function calls another, which eventually calls the first.

void A() { B(); } void B() { A(); }

Tail Recursion

The recursive call is the last operation.

void print(int n) { if (n == 0) return; cout << n; print(n - 1); }

The recursive call happens at the end.

16. When Is Recursion Useful?

Recursion becomes especially useful when a problem naturally contains smaller versions of itself.

Important applications:

🌳 Trees

Tree traversal is commonly written recursively.

10 / \ 5 20

🔍 Graphs

DFS can be implemented recursively.

🔄 Backtracking

Examples:

  • N-Queens
  • Sudoku
  • Maze
  • Permutations
  • Combinations

⚡ Divide and Conquer

Examples:

  • Merge Sort
  • Quick Sort
  • Binary Search

🧠 Dynamic Programming

Many DP problems can first be understood using recursion.

17. Common Recursion Problems

You should eventually be able to solve:

  1. Print 1 to N
  2. Print N to 1
  3. Sum of first N numbers
  4. Factorial
  5. Fibonacci
  6. Power of a number
  7. Reverse a string
  8. Check palindrome
  9. Sum of digits
  10. Count digits
  11. GCD using recursion
  12. Binary search recursively
  13. Generate subsequences
  14. Generate permutations
  15. Tower of Hanoi

The later problems connect recursion to backtracking, searching, trees, and divide-and-conquer.

18. The Most Important Recursion Pattern

When you see a recursion problem, think:

1. What is the smallest problem? ↓ 2. What is the BASE CASE? ↓ 3. How can I reduce the problem? ↓ 4. Call the function with the smaller problem.

For example, factorial:

Problem: factorial(n) Smallest problem: factorial(0) = 1 Reduce: factorial(n) = n × factorial(n-1)

So:

int factorial(int n) { // Base case if (n == 0) return 1; // Smaller problem return n * factorial(n - 1); }

🧠 Final Summary

Remember these 5 things:

Recursion = Function calling itself 1. Base Case ↓ Stops recursion 2. Recursive Case ↓ Function calls itself 3. Each call creates a stack frame 4. Calls go down → then return back up 5. Missing/incorrect base case → Stack Overflow

The connection with what you've already learned is important:

Stack ↓ Call Stack ↓ Recursion ↓ Backtracking ↓ Trees / Graphs ↓ Divide & Conquer ↓ Dynamic Programming

Next topic in your DSA roadmap:

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy