🟡 Intermediate · Lesson 19

Recursion

What is Recursion?

A function that calls itself is called a recursive function, and this technique is called recursion. Every recursive solution has two essential parts:

Base Case — The condition where the function stops calling itself (prevents infinite recursion)
Recursive Case — The part where the function calls itself with a smaller/simpler input

⚠️ Always Have a Base Case!

Without a base case, the function calls itself forever → stack overflow → program crash. Every recursive function MUST have a base case that eventually terminates.

How Recursion Works – Call Stack

Each recursive call is added to the call stack. When the base case is reached, functions return one by one (unwinding the stack).

Concept – Countdown

void countdown(int n) {
    if (n == 0) {                    // Base case
        printf("Blastoff!\n");
        return;
    }
    printf("%d... \n", n);
    countdown(n - 1);               // Recursive call
}
// countdown(3) → countdown(2) → countdown(1) → countdown(0)
// Then returns back: 0 done → 1 done → 2 done → 3 done

3... 2... 1... Blastoff!

Factorial using Recursion

Factorial: 5! = 5 × 4 × 3 × 2 × 1 = 120. Recursively: n! = n × (n-1)!, base: 0! = 1

C Language – Recursive Factorial

#include <stdio.h>

long long factorial(int n) {
    if (n <= 1) return 1;          // Base case: 0! = 1! = 1
    return n * factorial(n - 1);   // Recursive case
}

int main() {
    int n;
    printf("Enter n: ");
    scanf("%d", &n);
    printf("%d! = %lld\n", n, factorial(n));
    return 0;
}

Enter n: 6 6! = 720

How it works for factorial(4):

Trace

factorial(4)
  → 4 * factorial(3)
      → 3 * factorial(2)
          → 2 * factorial(1)
              → returns 1  (base case!)
          → returns 2 * 1 = 2
      → returns 3 * 2 = 6
  → returns 4 * 6 = 24

Fibonacci Series using Recursion

Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21... Each term = sum of previous two. F(n) = F(n-1) + F(n-2). Base: F(0) = 0, F(1) = 1

C Language – Recursive Fibonacci

#include <stdio.h>

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

int main() {
    int n;
    printf("How many terms? ");
    scanf("%d", &n);
    printf("Fibonacci: ");
    for (int i = 0; i < n; i++)
        printf("%d ", fibonacci(i));
    printf("\n");
    return 0;
}

How many terms? 8 Fibonacci: 0 1 1 2 3 5 8 13

Sum of Digits using Recursion

C Language

#include <stdio.h>

int sumDigits(int n) {
    if (n == 0) return 0;          // Base case
    return (n % 10) + sumDigits(n / 10); // Recursive
}

int main() {
    int num;
    printf("Enter number: ");
    scanf("%d", &num);
    printf("Sum of digits: %d\n", sumDigits(num));
    return 0;
}

Enter number: 12345 Sum of digits: 15

Power Function using Recursion

C Language – power(base, exp)

#include <stdio.h>

long long power(int base, int exp) {
    if (exp == 0) return 1;          // Base case: x^0 = 1
    return base * power(base, exp - 1); // x^n = x * x^(n-1)
}

int main() {
    printf("2^10 = %lld\n", power(2, 10));
    printf("3^5  = %lld\n", power(3, 5));
    return 0;
}

2^10 = 1024 3^5 = 243

Recursion vs Iteration

Feature	Recursion	Iteration (Loop)
Code length	Usually shorter	Can be longer
Readability	Better for tree/graph problems	Better for simple loops
Memory	More (call stack)	Less
Speed	Slower (function call overhead)	Faster
Risk	Stack overflow if no base case	Infinite loop if bad condition
Best for	Trees, graphs, divide & conquer	Simple counting, arrays

Summary

Recursion = a function calling itself
Every recursive function needs: Base Case + Recursive Case
Without a base case → infinite recursion → stack overflow
Each call is added to the call stack; base case unwinds it
Common recursive problems: factorial, Fibonacci, sum of digits, power, GCD
Use iteration when performance matters; use recursion when clarity matters

🏋️ Practice

Write recursive functions: (1) GCD of two numbers (2) Reverse a string (3) Check if string is palindrome (4) Binary search (5) Print all permutations of a string

Recursion क्या है?

जो function खुद को ही call करे उसे recursive function कहते हैं, और इस technique को recursion कहते हैं। हर recursive solution में दो ज़रूरी parts होते हैं:

Base Case — वो condition जहाँ function खुद को call करना बंद कर देता है (infinite recursion रोकता है)
Recursive Case — जहाँ function खुद को smaller input के साथ call करता है

⚠️ Base Case ज़रूरी है!

Base case के बिना, function खुद को हमेशा के लिए call करेगा → stack overflow → crash! हर recursive function में base case होना चाहिए।

Recursion कैसे काम करती है

हर recursive call call stack में add होती है। Base case पर पहुँचने पर functions एक-एक करके return होते हैं (stack unwind होती है)।

Concept – Countdown

void countdown(int n) {
    if (n == 0) { printf("Blast off!\n"); return; }  // Base case
    printf("%d...\n", n);
    countdown(n - 1);   // Recursive call
}
// countdown(3) → countdown(2) → countdown(1) → countdown(0)
// फिर वापस: 0 done → 1 done → 2 done → 3 done

Factorial – Recursion से

Factorial: 5! = 5 × 4 × 3 × 2 × 1 = 120. Recursively: n! = n × (n-1)!, base: 0! = 1

C Language – Recursive Factorial

#include <stdio.h>

long long factorial(int n) {
    if (n <= 1) return 1;          // Base case
    return n * factorial(n - 1);   // Recursive case
}

int main() {
    int n;
    printf("n daalen: ");
    scanf("%d", &n);
    printf("%d! = %lld\n", n, factorial(n));
    return 0;
}

n daalen: 6 6! = 720

factorial(4) कैसे काम करता है:

Trace

factorial(4)
  → 4 * factorial(3)
      → 3 * factorial(2)
          → 2 * factorial(1)
              → 1 return (base case!)
          → 2 * 1 = 2 return
      → 3 * 2 = 6 return
  → 4 * 6 = 24 return

Fibonacci Series – Recursion से

Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13... हर term = पिछले दो terms का जोड़। F(n) = F(n-1) + F(n-2)। Base: F(0)=0, F(1)=1

C Language

#include <stdio.h>

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

int main() {
    int n;
    printf("Kitne terms chahiye? ");
    scanf("%d", &n);
    printf("Fibonacci: ");
    for (int i = 0; i < n; i++)
        printf("%d ", fibonacci(i));
    printf("\n");
    return 0;
}

Kitne terms chahiye? 8 Fibonacci: 0 1 1 2 3 5 8 13

अंकों का जोड़ – Recursion से

C Language

int ankJod(int n) {
    if (n == 0) return 0;          // Base case
    return (n % 10) + ankJod(n / 10); // Recursive
}
// ankJod(12345) = 5 + ankJod(1234)
//               = 5 + 4 + ankJod(123)
//               = 5+4+3+2+1 = 15

सारांश

Recursion = function का खुद को call करना
हर recursive function में होना चाहिए: Base Case + Recursive Case
Base case के बिना → infinite recursion → stack overflow
Common recursive problems: factorial, Fibonacci, sum of digits, power, GCD
Performance ज़रूरी हो तो iteration use करें; clarity के लिए recursion बेहतर

🏋️ Practice

Recursive functions लिखें: (1) GCD (2) String reverse (3) Palindrome check (4) किसी array का sum (5) n तक prime numbers print करें

← Back to C Tutorial