Day 53: Recursion | Fibonacci & Head vs Tail Recursion 🐇

📅 Date: Jan 16, 2026

🧠 Mood: Time Traveler ⏳

🔥 Topic: DSA: Recursion (Head vs Tail & Fibonacci)

🔄 Head vs Tail Recursion

Recursion is not just about calling a function. When you do the work matters.

1. Tail Recursion (Going Down)

You work BEFORE the recursive call.

void print(int n) {
    if(n==0) return;
    cout << n << endl; // Work first
    print(n-1);        // Call last
}

Output: 5 4 3 2 1 (Descending)

2. Head Recursion (Coming Up)

You work AFTER the recursive call returns.

void print(int n) {
    if(n==0) return;
    print(n-1);        // Call first
    cout << n << endl; // Work later
}

Output: 1 2 3 4 5 (Ascending)

Why? In Head Recursion, the print statement waits in the Stack memory until the base case hits, then it prints while returning (Backtracking).

---

🐇 The Fibonacci Series

The most famous example of Recursion.
Sequence: 0, 1, 1, 2, 3, 5, 8, 13...

Logic: Any number is the sum of the previous two numbers.
f(n) = f(n-1) + f(n-2)

💻 Code: Nth Fibonacci Number

#include <iostream>
using namespace std;

int fib(int n) {
    // 1. BASE CASE
    if(n == 0) return 0;
    if(n == 1) return 1;

    // 2. RECURSIVE RELATION
    // This creates a Tree structure of calls
    return fib(n-1) + fib(n-2);
}

int main() {
    int n = 6;
    cout << "The " << n << "th Fibonacci number is: " << fib(n);
    return 0;
}

Output: 8 (Because 0,1,1,2,3,5,8)

---

⚠️ The Danger Zone (Time Complexity)

Look at the code fib(n-1) + fib(n-2). It calls itself TWICE.
This creates a massive tree.

• To find fib(5), it calculates fib(3) multiple times!
• This is O(2^n) (Exponential Time). It's very slow for large numbers.
• We will fix this later using Dynamic Programming (DP). For now, understand the flow.

---

🚀 Day 53 Challenge

1. Write a recursive function power(2, n) using the logic 2 * power(2, n-1).
2. Climb Stairs Problem: You can take 1 step or 2 steps. How many ways to reach the Nth stair?
   Hint: It's exactly the same as Fibonacci! Try to figure out why.

Next Up: Day 54 - Recursion with Strings (Checking Palindrome).