C++ में Recursion

Recursion तब होता है जब एक function एक बड़ी problem को इसके एक छोटे हिस्से पर खुद को call करके solve करता है, अंदर छोटी dolls वाली nesting dolls की तरह। यह सबसे छोटी doll पर रुकता है।

In this page:

Recursion का Introduction
Base Case और Recursive Case
Fibonacci Series
Stack Safety
Iterative बनाम Recursive

Syntax

cpp

return_type function_name(parameters) {
  if (base_case_condition) {
    return base_value;
  }
  return function_name(smaller_input);  // recursive case
}

Recursion का Introduction

Recursion तब होता है जब एक function खुद को call करता है, repetition control करने के लिए एक loop की condition की बजाय function calls इस्तेमाल करते हुए।

हर call original problem के एक छोटे हिस्से पर काम करती है, और progress एक loop counter increment होने की बजाय हर call पर बदलते arguments के जरिए होता है।

उदाहरण: Introduction to Recursion

cpp

// Include std::cout and std::cin
#include <iostream>

int countdown(int n) {
	if (n == 0) return 0;
	// Print to the console with cout
	std::cout << n << " ";
	// Send countdown(n - 1) back to the caller
	return countdown(n - 1);
}

// Program execution starts in main()
int main() {
	countdown(5);
	// Print to the console with cout
	std::cout << std::endl;
	// Return 0 to signal that the program finished successfully
	return 0;
}

Base Case और Recursive Case

हर recursive function को एक base case चाहिए — एक condition जहाँ यह खुद को call करना बंद कर देता है और बस सीधे एक value return करता है — इसके बिना, function stack memory खत्म होने और crash होने तक indefinitely खुद को call करता रहेगा।

Recursive case वह हिस्सा है जो function को दोबारा call करता है, हमेशा उस base case के करीब move करते हुए।

उदाहरण: Base Case and Recursive Case

cpp

#include <iostream>

int factorial(int n) {
	if (n == 0) return 1;        // base case
	return n * factorial(n - 1); // recursive case
}

int main() {
	std::cout << factorial(5) << std::endl;
	return 0;
}

Fibonacci Series

Fibonacci sequence, जहाँ हर number इससे पहले के दो का sum है, naturally recursion पर map होता है: fib(n) = fib(n-1) + fib(n-2), fib(0) और fib(1) base cases के साथ।

यह लगभग exactly mathematical definition को mirror करता है, यही एक कारण है कि यहाँ recursion elegant महसूस होता है भले ही यह सबसे efficient implementation न हो।

उदाहरण: Fibonacci Series

cpp

// Include std::cout and std::cin
#include <iostream>

int fib(int n) {
	if (n <= 1) return n;
	// Send fib(n - 1) + fib(n - 2) back to the caller
	return fib(n - 1) + fib(n - 2);
}

// Program execution starts in main()
int main() {
	// Loop: repeat while the condition holds
	for (int i = 0; i < 8; i++) {
		// Print to the console with cout
		std::cout << fib(i) << " ";
	}
	// Print to the console with cout
	std::cout << std::endl;
	// Return 0 to signal that the program finished successfully
	return 0;
}

Stack Safety

हर recursive call उस call के local variables और बाद में कहाँ resume करना है यह track करने के लिए program के call stack में एक नया frame add करती है, और बहुत सारे unfinished calls (deep recursion) stack करना available stack memory खत्म कर सकता है, एक stack overflow crash cause करते हुए।

यही वजह है कि recursive solutions को एक base case चाहिए जो एक reasonable संख्या में calls के अंदर reliably पहुंचा जाए।

उदाहरण: Stack Safety

cpp

#include <iostream>

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

int main() {
	std::cout << sumTo(1000) << std::endl;
	// sumTo(1000000); // risks stack overflow: too many stacked call frames
	return 0;
}

Iterative बनाम Recursive

लगभग कोई भी recursive algorithm इसकी बजाय एक iterative loop की तरह दोबारा लिखा जा सकता है, और iterative versions आमतौर पर तेज़ होते हैं और काफी कम memory इस्तेमाल करते हैं, क्योंकि वे repeated function calls और stack frames के overhead से बचते हैं।

Recursion फिर भी अक्सर तब चुना जाता है जब यह code की logic को dramatically clearer बनाता है, जैसे tree traversal के साथ।

उदाहरण: Iterative vs Recursive

cpp

// Include std::cout and std::cin
#include <iostream>

int factorialRecursive(int n) {
	if (n == 0) return 1;
	// Send n * factorialRecursive(n - 1) back to the caller
	return n * factorialRecursive(n - 1);
}

int factorialIterative(int n) {
	// Declare result and set it to 1
	int result = 1;
	// Loop: repeat while the condition holds
	for (int i = 1; i <= n; i++) {
		result *= i;
	}
	// Send result back to the caller
	return result;
}

// Program execution starts in main()
int main() {
	// Print to the console with cout
	std::cout << factorialRecursive(5) << " " << factorialIterative(5) << std::endl;
	// Return 0 to signal that the program finished successfully
	return 0;
}

Chapter Quiz — Complete all 13 topics to unlock

0/13 topics done

Complete these topics first:

← Previous Lesson C++ Function Overloading Next Lesson → C++ Inline Functions