Recursion की गहराई से समझ

Recursion खुद की एक छोटी version से वही सवाल पूछने जैसा काम करता है, यह भरोसा करते हुए कि यह जवाब देगी, जब तक आप एक इतना छोटा सवाल न पहुंचें जिसका obvious answer हो।

In this page:

Recursion Basics
Base Case
Recursive Flow
Recursive Arrays
Recursion Practice

Syntax

markup

def recursive_function(input):
    if base_condition:
        return base_value
    return combine(recursive_function(smaller_input))

Recursion Basics

एक recursive function उसी problem के एक छोटे version पर खुद को call करके problem solve करता है, सभी in-progress calls track करने के लिए language के call stack पर भरोसा करते हुए। यह repetition express करने का एक loop से अलग तरीका है, अक्सर problem की खुद की natural structure से मेल खाते हुए (जैसे trees या nested data)।

उदाहरण: Recursion Basics

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

public class Main {
	static void countDown(int n) {
		if (n <= 0) return;
		System.out.print(n + " ");
		countDown(n - 1);
	}
	public static void main(String[] args) {
		countDown(5);
	}
}

def count_down(n):
    if n <= 0:
        return
    print(n, end=" ")
    count_down(n - 1)

count_down(5)

#include <stdio.h>
void countDown(int n) {
	if (n <= 0) return;
	printf("%d ", n);
	countDown(n - 1);
}
int main() {
	countDown(5);
	return 0;
}

Base Case

हर recursive function को एक base case चाहिए जो बिना एक और recursive call किए सीधे एक value return करे, नहीं तो calls कभी नहीं रुकेंगी और program एक stack overflow के साथ crash हो जाएगा। Base case को सही पाना आमतौर पर correct recursion लिखने का सबसे मुश्किल और सबसे महत्वपूर्ण हिस्सा है।

उदाहरण: Base Case

#include <iostream>
using namespace std;
int sumTo(int n) {
	if (n == 0) return 0;
	return n + sumTo(n - 1);
}
int main() {
	cout << sumTo(4);
	return 0;
}

public class Main {
	static int sumTo(int n) {
		if (n == 0) return 0;
		return n + sumTo(n - 1);
	}
	public static void main(String[] args) {
		System.out.println(sumTo(4));
	}
}

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

print(sum_to(4))

#include <stdio.h>
int sumTo(int n) {
	if (n == 0) return 0;
	return n + sumTo(n - 1);
}
int main() {
	printf("%d", sumTo(4));
	return 0;
}

Recursive Flow

जब कोई function खुद को call करता है, वह call call stack में push हो जाती है और current call तब तक रुकती है जब तक नई एक result return नहीं करती। Execution हर paused call से उल्टे order में वापस unwind होता है, यही कारण है कि recursive traces अक्सर 'वापस ऊपर जाते हुए' काम होते दिखाते हैं।

उदाहरण: Recursive Flow

#include <iostream>
using namespace std;
void trace(int n) {
	if (n == 0) { cout << "reached base" << endl; return; }
	cout << "entering " << n << endl;
	trace(n - 1);
	cout << "leaving " << n << endl;
}
int main() {
	trace(3);
	return 0;
}

public class Main {
	static void trace(int n) {
		if (n == 0) { System.out.println("reached base"); return; }
		System.out.println("entering " + n);
		trace(n - 1);
		System.out.println("leaving " + n);
	}
	public static void main(String[] args) {
		trace(3);
	}
}

def trace(n):
    if n == 0:
        print("reached base")
        return
    print("entering", n)
    trace(n - 1)
    print("leaving", n)

trace(3)

#include <stdio.h>
void trace(int n) {
	if (n == 0) { printf("reached base\n"); return; }
	printf("entering %d\n", n);
	trace(n - 1);
	printf("leaving %d\n", n);
}
int main() {
	trace(3);
	return 0;
}

Recursive Arrays

Arrays या lists को element by element process करने के लिए Recursion एक natural fit है: पहला element handle करें, फिर list के बाकी हिस्से को उसी problem के एक छोटे version के रूप में recursively handle करें। यह mirror करता है कि कई list operations mathematically कैसे defined हैं।

उदाहरण: Recursive Arrays

#include <iostream>
using namespace std;
int sumArray(int arr[], int n) {
	if (n == 0) return 0;
	return arr[0] + sumArray(arr + 1, n - 1);
}
int main() {
	int arr[] = {1, 2, 3, 4};
	cout << sumArray(arr, 4);
	return 0;
}

public class Main {
	static int sumArray(int[] arr, int i) {
		if (i == arr.length) return 0;
		return arr[i] + sumArray(arr, i + 1);
	}
	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4};
		System.out.println(sumArray(arr, 0));
	}
}

def sum_array(arr):
    if not arr:
        return 0
    return arr[0] + sum_array(arr[1:])

print(sum_array([1, 2, 3, 4]))

#include <stdio.h>
int sumArray(int arr[], int n) {
	if (n == 0) return 0;
	return arr[0] + sumArray(arr + 1, n - 1);
}
int main() {
	int arr[] = {1, 2, 3, 4};
	printf("%d", sumArray(arr, 4));
	return 0;
}

Recursion Practice

एक strong recursive solution को हर call के साथ base case की ओर clear progress दिखानी चाहिए — आमतौर पर input को कम से कम एक element से छोटा करके या इसे आधा करके। अगर आप स्पष्ट रूप से नहीं बता सकते कि हर call में specifically क्या छोटा होता है, recursion शायद सही से terminate नहीं होगा।

उदाहरण: Recursion Practice

#include <iostream>
using namespace std;
int countDigits(int n) {
	if (n < 10) return 1;
	return 1 + countDigits(n / 10);
}
int main() {
	cout << countDigits(4521);
	return 0;
}

public class Main {
	static int countDigits(int n) {
		if (n < 10) return 1;
		return 1 + countDigits(n / 10);
	}
	public static void main(String[] args) {
		System.out.println(countDigits(4521));
	}
}

def count_digits(n):
    if n < 10:
        return 1
    return 1 + count_digits(n // 10)

print(count_digits(4521))

#include <stdio.h>
int countDigits(int n) {
	if (n < 10) return 1;
	return 1 + countDigits(n / 10);
}
int main() {
	printf("%d", countDigits(4521));
	return 0;
}

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Frequency Counting Next Lesson → Fibonacci and Factorial