← Back to DSA Course | Chapter 1: Introduction & Complexity | Lesson 5 of 6

Recursion की मूल बातें

Recursion Russian nesting dolls के एक set जैसा है: बड़ी वाली खोलने के लिए आप इसके अंदर एक छोटी खोलते हैं, वगैरह, जब तक आप उस tiny doll तक न पहुंचें जो आपको रोकती है।

In this page:

  1. What is Recursion
  2. Base Case
  3. Recursive Step
  4. Call Stack
  5. Simple Recursive Problems
Syntax
markup 
def recursive_function(n):
    if n == base_value:      # base case
        return base_result
    return recursive_function(n - 1)   # recursive step

What is Recursion

Recursion एक technique है जहां एक function उसी problem के एक छोटे version पर खुद को call करके problem solve करता है, जब तक pieces सीधे answer देने लायक simple न हो जाएं। यह mirror करता है कि कई problems naturally कैसे define होती हैं, एक folder जिसमें files और दूसरे folders हों जैसा।

उदाहरण: What is Recursion

#include <iostream>
using namespace std;
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}
int main() {
    cout << "factorial(5): " << factorial(5) << endl;
    return 0;
}
public class Main {
    static int factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }
    public static void main(String[] args) {
        System.out.println("factorial(5): " + factorial(5));
    }
}
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print("factorial(5):", factorial(5))
#include <stdio.h>
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}
int main() {
    printf("factorial(5): %d\n", factorial(5));
    return 0;
}

Base Case

Base case problem का सबसे simple version है जिसे function बिना आगे recurse किए तुरंत answer दे सकता है। हर recursive function को कम से कम एक base case चाहिए, नहीं तो यह crash होने तक खुद को हमेशा के लिए call करता रहेगा।

उदाहरण: Base Case

#include <iostream>
using namespace std;
int countdown(int n) {
    if (n <= 0) return 0; // base case: stops the recursion
    cout << n << " ";
    return countdown(n - 1);
}
int main() {
    countdown(5);
    cout << "done" << endl;
    return 0;
}
public class Main {
    static int countdown(int n) {
        if (n <= 0) return 0; // base case: stops the recursion
        System.out.print(n + " ");
        return countdown(n - 1);
    }
    public static void main(String[] args) {
        countdown(5);
        System.out.println("done");
    }
}
def countdown(n):
    if n <= 0:  # base case: stops the recursion
        return
    print(n, end=" ")
    countdown(n - 1)

countdown(5)
print("done")
#include <stdio.h>
void countdown(int n) {
    if (n <= 0) return; /* base case: stops the recursion */
    printf("%d ", n);
    countdown(n - 1);
}
int main() {
    countdown(5);
    printf("done\n");
    return 0;
}

Recursive Step

Recursive step वह है जहां function खुद को एक input के साथ call करता है जो base case के करीब जाने की guarantee रखता है, जैसे n के बजाय n-1, या किसी array का एक छोटा slice। इस step को गलत करना recursion bugs का सबसे आम source है।

उदाहरण: Recursive Step

#include <iostream>
using namespace std;
int sumDigits(int n) {
    if (n == 0) return 0;
    return (n % 10) + sumDigits(n / 10); // moves closer to base case each call
}
int main() {
    cout << "sumDigits(1234): " << sumDigits(1234) << endl;
    return 0;
}
public class Main {
    static int sumDigits(int n) {
        if (n == 0) return 0;
        return (n % 10) + sumDigits(n / 10); // moves closer to base case
    }
    public static void main(String[] args) {
        System.out.println("sumDigits(1234): " + sumDigits(1234));
    }
}
def sum_digits(n):
    if n == 0:
        return 0
    return (n % 10) + sum_digits(n // 10)  # moves closer to base case

print("sum_digits(1234):", sum_digits(1234))
#include <stdio.h>
int sumDigits(int n) {
    if (n == 0) return 0;
    return (n % 10) + sumDigits(n / 10); /* moves closer to base case */
}
int main() {
    printf("sumDigits(1234): %d\n", sumDigits(1234));
    return 0;
}

Call Stack

हर recursive call call stack में एक नया frame जोड़ता है, उस call के local variables और इसका return address रखते हुए, और calls return होने पर frames उल्टे order में unwind होते हैं। यही कारण है कि deep recursion memory-hungry हो सकता है और, extreme cases में, एक stack overflow का कारण बन सकता है।

उदाहरण: Call Stack

#include <iostream>
using namespace std;
int trace(int n) {
    cout << "entering trace(" << n << ")" << endl;
    if (n == 0) return 0;
    int result = n + trace(n - 1);
    cout << "returning from trace(" << n << ")" << endl;
    return result;
}
int main() {
    cout << "Total: " << trace(3) << endl;
    return 0;
}
public class Main {
    static int trace(int n) {
        System.out.println("entering trace(" + n + ")");
        if (n == 0) return 0;
        int result = n + trace(n - 1);
        System.out.println("returning from trace(" + n + ")");
        return result;
    }
    public static void main(String[] args) {
        System.out.println("Total: " + trace(3));
    }
}
def trace(n):
    print(f"entering trace({n})")
    if n == 0:
        return 0
    result = n + trace(n - 1)
    print(f"returning from trace({n})")
    return result

print("Total:", trace(3))
#include <stdio.h>
int trace(int n) {
    printf("entering trace(%d)\n", n);
    if (n == 0) return 0;
    int result = n + trace(n - 1);
    printf("returning from trace(%d)\n", n);
    return result;
}
int main() {
    printf("Total: %d\n", trace(3));
    return 0;
}

Simple Recursive Problems

Recursion उन problems पर चमकता है जो naturally self-similar या nested हैं, जैसे tree traversal, divide-and-conquer algorithms, और backtracking, जहां solution को recursively express करना अक्सर explicit loops और एक manual stack से लिखने से कहीं छोटा और clearer होता है।

उदाहरण: Simple Recursive Problems

#include <iostream>
using namespace std;
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // naturally self-similar problem
}
int main() {
    cout << "fib(6): " << fib(6) << endl;
    return 0;
}
public class Main {
    static int fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2); // naturally self-similar problem
    }
    public static void main(String[] args) {
        System.out.println("fib(6): " + fib(6));
    }
}
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)  # naturally self-similar problem

print("fib(6):", fib(6))
#include <stdio.h>
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); /* naturally self-similar problem */
}
int main() {
    printf("fib(6): %d\n", fib(6));
    return 0;
}
Related Topics

Recursion और Iteration में अंतर · Recursion की गहराई से समझ · Best, Worst और Average Case · Space Complexity क्या है

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. Base case भूल जाना, इसलिए function खुद को हमेशा के लिए call करता है और एक stack overflow में खत्म होता है।
  2. एक recursive call लिखना जो base case की ओर नहीं बढ़ता, जैसे factorial(n - 1) के बजाय factorial(n)।
  3. एक base case उपयोग करना जो एक input miss करता है, जैसे सिर्फ n == 1 handle करना ताकि factorial(0) negative numbers में recurse करे।
🔒

Chapter Quiz — Complete all 6 topics to unlock

0/6 topics done

Complete these topics first:

← Previous Lesson Best Worst and Average Case Next Lesson → Recursion vs Iteration

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.