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

Recursion और Iteration में अंतर

Recursion और iteration वही chore बार-बार करने के दो तरीके हैं: recursion आपकी मदद के लिए खुद की एक छोटी copy से पूछता है, जबकि iteration बस एक loop के आस-पास चलता है।

In this page:

  1. Basic Difference
  2. Factorial
  3. Sum of Numbers
  4. Memory Difference
  5. When to Use Which
Syntax
markup 
# Recursive
def solve(n):
    if n <= 1:
        return 1
    return n * solve(n - 1)

# Iterative
def solve(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Basic Difference

Recursion किसी problem को एक function से खुद को छोटे subproblems पर call करके solve करता है, जबकि iteration इसे एक condition पूरी होने तक एक loop में code का एक block दोहराकर solve करता है। दोनों बिल्कुल वही logic implement कर सकते हैं; वे सिर्फ repetition को अलग तरीके से structure करते हैं।

उदाहरण: Basic Difference

#include <iostream>
using namespace std;
int factRecursive(int n) {
    if (n <= 1) return 1;
    return n * factRecursive(n - 1);
}
int factIterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}
int main() {
    cout << "Recursive: " << factRecursive(5) << ", Iterative: " << factIterative(5) << endl;
    return 0;
}
public class Main {
    static int factRecursive(int n) {
        if (n <= 1) return 1;
        return n * factRecursive(n - 1);
    }
    static int factIterative(int n) {
        int result = 1;
        for (int i = 2; i <= n; i++) result *= i;
        return result;
    }
    public static void main(String[] args) {
        System.out.println("Recursive: " + factRecursive(5) + ", Iterative: " + factIterative(5));
    }
}
def fact_recursive(n):
    if n <= 1:
        return 1
    return n * fact_recursive(n - 1)

def fact_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print("Recursive:", fact_recursive(5), ", Iterative:", fact_iterative(5))
#include <stdio.h>
int factRecursive(int n) {
    if (n <= 1) return 1;
    return n * factRecursive(n - 1);
}
int factIterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}
int main() {
    printf("Recursive: %d, Iterative: %d\n", factRecursive(5), factIterative(5));
    return 0;
}

Factorial

एक factorial recursively compute करना n को factorial(n-1) से multiply करता है 1 के एक base case तक, जो लगभग mathematical definition जैसा पढ़ता है। Iterative version एक loop और एक accumulator variable उपयोग करता है, और किसी function-call overhead के बिना वही multiplications करता है।

उदाहरण: Factorial

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

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

Sum of Numbers

Numbers की एक list sum करना एक और problem है जो दोनों तरीकों से solvable है: recursively पहले element को बाकी के sum में जोड़ें, या iteratively एक loop में हर element को एक running total में जोड़ें। Results identical हैं, लेकिन recursive version process किए गए हर element के लिए ज़्यादा memory उपयोग करता है।

उदाहरण: Sum of Numbers

#include <iostream>
using namespace std;
int sumRecursive(int arr[], int n) {
    if (n == 0) return 0;
    return arr[n - 1] + sumRecursive(arr, n - 1);
}
int sumIterative(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) total += arr[i];
    return total;
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    cout << "Recursive: " << sumRecursive(arr, 5) << ", Iterative: " << sumIterative(arr, 5) << endl;
    return 0;
}
public class Main {
    static int sumRecursive(int[] arr, int n) {
        if (n == 0) return 0;
        return arr[n - 1] + sumRecursive(arr, n - 1);
    }
    static int sumIterative(int[] arr) {
        int total = 0;
        for (int x : arr) total += x;
        return total;
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println("Recursive: " + sumRecursive(arr, arr.length) + ", Iterative: " + sumIterative(arr));
    }
}
def sum_recursive(arr):
    if not arr:
        return 0
    return arr[0] + sum_recursive(arr[1:])

def sum_iterative(arr):
    total = 0
    for x in arr:
        total += x
    return total

arr = [1, 2, 3, 4, 5]
print("Recursive:", sum_recursive(arr), ", Iterative:", sum_iterative(arr))
#include <stdio.h>
int sumRecursive(int arr[], int n) {
    if (n == 0) return 0;
    return arr[n - 1] + sumRecursive(arr, n - 1);
}
int sumIterative(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) total += arr[i];
    return total;
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    printf("Recursive: %d, Iterative: %d\n", sumRecursive(arr, 5), sumIterative(arr, 5));
    return 0;
}

Memory Difference

Iteration आमतौर पर extra memory की एक छोटी, constant मात्रा उपयोग करता है (सिर्फ loop variables), जबकि recursion इसकी depth के अनुपात में stack space consume करता है, क्योंकि हर call return होने तक stack पर रहती है। बहुत deep recursion के लिए, यह performance और यहां तक कि correctness के लिए बहुत मायने रख सकता है।

उदाहरण: Memory Difference

#include <iostream>
using namespace std;
int sumRecursive(int n) {
    if (n == 0) return 0; // uses stack space proportional to depth: O(n)
    return n + sumRecursive(n - 1);
}
int sumIterative(int n) {
    int total = 0; // constant extra memory: O(1)
    for (int i = 1; i <= n; i++) total += i;
    return total;
}
int main() {
    cout << "Recursive (O(n) space): " << sumRecursive(5) << endl;
    cout << "Iterative (O(1) space): " << sumIterative(5) << endl;
    return 0;
}
public class Main {
    static int sumRecursive(int n) {
        if (n == 0) return 0; // O(n) stack space
        return n + sumRecursive(n - 1);
    }
    static int sumIterative(int n) {
        int total = 0; // O(1) space
        for (int i = 1; i <= n; i++) total += i;
        return total;
    }
    public static void main(String[] args) {
        System.out.println("Recursive (O(n) space): " + sumRecursive(5));
        System.out.println("Iterative (O(1) space): " + sumIterative(5));
    }
}
def sum_recursive(n):
    if n == 0:
        return 0  # O(n) stack space
    return n + sum_recursive(n - 1)

def sum_iterative(n):
    total = 0  # O(1) space
    for i in range(1, n + 1):
        total += i
    return total

print("Recursive (O(n) space):", sum_recursive(5))
print("Iterative (O(1) space):", sum_iterative(5))
#include <stdio.h>
int sumRecursive(int n) {
    if (n == 0) return 0; /* O(n) stack space */
    return n + sumRecursive(n - 1);
}
int sumIterative(int n) {
    int total = 0; /* O(1) space */
    for (int i = 1; i <= n; i++) total += i;
    return total;
}
int main() {
    printf("Recursive (O(n) space): %d\n", sumRecursive(5));
    printf("Iterative (O(1) space): %d\n", sumIterative(5));
    return 0;
}

When to Use Which

Recursion तब चुनें जब यह problem की structure clearer बनाता हो, जैसे trees या divide-and-conquer, और iteration तब चुनें जब performance या stack depth चिंता का विषय हो, जैसे बहुत बड़ी flat lists process करना। कई languages आपको ज़रूरत पड़ने पर एक को दूसरे में convert करने देती हैं।

उदाहरण: When to Use Which

#include <iostream>
using namespace std;
// Recursion: clearer for naturally nested structure, like tree depth.
int treeDepth(int nodes[], int i, int n) {
    if (i >= n) return 0;
    int left = treeDepth(nodes, 2 * i + 1, n);
    int right = treeDepth(nodes, 2 * i + 2, n);
    return 1 + max(left, right);
}
int main() {
    int nodes[] = {1, 2, 3, 4, 5, 6, 7};
    cout << "Tree depth (recursion fits naturally): " << treeDepth(nodes, 0, 7) << endl;
    return 0;
}
public class Main {
    // Recursion: clearer for naturally nested structure, like tree depth.
    static int treeDepth(int[] nodes, int i, int n) {
        if (i >= n) return 0;
        int left = treeDepth(nodes, 2 * i + 1, n);
        int right = treeDepth(nodes, 2 * i + 2, n);
        return 1 + Math.max(left, right);
    }
    public static void main(String[] args) {
        int[] nodes = {1, 2, 3, 4, 5, 6, 7};
        System.out.println("Tree depth (recursion fits naturally): " + treeDepth(nodes, 0, 7));
    }
}
# Recursion: clearer for naturally nested structure, like tree depth.
def tree_depth(nodes, i, n):
    if i >= n:
        return 0
    left = tree_depth(nodes, 2 * i + 1, n)
    right = tree_depth(nodes, 2 * i + 2, n)
    return 1 + max(left, right)

nodes = [1, 2, 3, 4, 5, 6, 7]
print("Tree depth (recursion fits naturally):", tree_depth(nodes, 0, 7))
#include <stdio.h>
int maxInt(int a, int b) { return a > b ? a : b; }
int treeDepth(int nodes[], int i, int n) {
    if (i >= n) return 0;
    int left = treeDepth(nodes, 2 * i + 1, n);
    int right = treeDepth(nodes, 2 * i + 2, n);
    return 1 + maxInt(left, right);
}
int main() {
    int nodes[] = {1, 2, 3, 4, 5, 6, 7};
    printf("Tree depth (recursion fits naturally): %d\n", treeDepth(nodes, 0, 7));
    return 0;
}
Related Topics

Recursion की मूल बातें · 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. एक साधारण loop के लिए deep recursion उपयोग करना, जैसे 100,000 numbers को sum करना, जो call stack overflow कर सकता है जबकि एक loop constant memory उपयोग करता है।
  2. यह मान लेना कि recursion iteration से तेज़ है, जब हर call overhead और stack usage जोड़ती है।
  3. एक recursion को एक loop में convert करना लेकिन loop variable update करना भूल जाना, इसलिए loop कभी खत्म नहीं होता।
चैप्टर सारांश
  • DSA यह study करता है कि data कैसे organize करें और efficient algorithms कैसे लिखें।
  • Time और space complexity, Big O notation से described, measure करते हैं कि एक algorithm कैसे scale होता है, और best, worst, और average cases इसका behavior describe करते हैं।
  • Recursion खुद को call करके problems solve करता है, और इसे iteration के साथ compare किया जा सकता है।
🔒

Chapter Quiz — Complete all 6 topics to unlock

0/6 topics done

Complete these topics first:

← Previous Lesson Recursion Basics Next Lesson → Array Introduction

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.