C में Recursion

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

In this page:

Recursion क्या है?
Base Case
Recursive Factorial
पहले N Numbers का Sum
Stack Overflow Warning

Syntax

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

Recursion क्या है?

Recursion तब होता है जब एक function खुद को, directly या indirectly, call करता है, आपको एक solution को same problem के एक छोटे version की तरह express करने देते हुए -- उन tasks के लिए useful जो naturally repeated, self-similar steps में टूटते हैं।

उदाहरण: What is Recursion?

// Include standard input/output (printf, scanf)
#include <stdio.h>
void countdown(int n) {
	if (n == 0) return;
	// Print formatted text to the screen
	printf("%d ", n);
	countdown(n - 1);
}
// Program execution starts in main()
int main() {
	countdown(3);
	// Return 0 to signal that the program finished successfully
	return 0;
}

Base Case

हर recursive function को एक base case चाहिए -- एक condition जहाँ यह खुद को call करना बंद कर देता है और बस एक value return करता है -- इसके बिना, हर call तब तक अगली call spawn करता रहता है जब तक program crash न हो जाए।

उदाहरण: The Base Case

// Include standard input/output (printf, scanf)
#include <stdio.h>
int factorial(int n) {
	// Check whether n == 0
	if (n == 0) {
		// Send 1 back to the caller
		return 1;
	}
	// Send n * factorial(n - 1) back to the caller
	return n * factorial(n - 1);
}
// Program execution starts in main()
int main() {
	// Print formatted text to the screen
	printf("%d", factorial(4));
	// Return 0 to signal that the program finished successfully
	return 0;
}

Recursive Factorial

एक factorial recursively compute करना N! को N गुणा (N-1)! की तरह express करता है, base case के साथ कि 0! 1 के बराबर है -- हर recursive call पिछले से एक step छोटा handle करता है जब तक यह उस stopping point तक न पहुंचे।

उदाहरण: Recursive Factorial

// Include standard input/output (printf, scanf)
#include <stdio.h>
int factorial(int n) {
	// Check whether n == 0
	if (n == 0) {
		// Send 1 back to the caller
		return 1;
	}
	// Send n * factorial(n - 1) back to the caller
	return n * factorial(n - 1);
}
// Program execution starts in main()
int main() {
	// Print formatted text to the screen
	printf("%d", factorial(5));
	// Return 0 to signal that the program finished successfully
	return 0;
}

पहले N Numbers का Sum

1 से N तक numbers को recursively sum करना same तरह काम करता है: N का sum N plus (N-1) का sum है, हर call में problem को एक-एक करके तब तक shrink करते हुए जब तक यह 0 या 1 के base case तक न पहुंचे।

उदाहरण: Sum of First N Numbers

// Include standard input/output (printf, scanf)
#include <stdio.h>
int sum(int n) {
	// Check whether n <= 1
	if (n <= 1) {
		// Send n back to the caller
		return n;
	}
	// Send n + sum(n - 1) back to the caller
	return n + sum(n - 1);
}
// Program execution starts in main()
int main() {
	// Print formatted text to the screen
	printf("%d", sum(5));
	// Return 0 to signal that the program finished successfully
	return 0;
}

Stack Overflow Warning

हर recursive call अपने local variables और return address track करने के लिए program के call stack पर अपनी जगह reserve करता है; recursion जो कभी अपने base case तक नहीं पहुंचता (या बहुत गहरा जाता है) उस stack को खत्म कर देता है और एक stack overflow के साथ crash हो जाता है।

उदाहरण: Stack Overflow Warning

// Include standard input/output (printf, scanf)
#include <stdio.h>
int factorial(int n) {
	// Check whether n == 0
	if (n == 0) {
		// Send 1 back to the caller
		return 1;
	}
	// Send n * factorial(n - 1) back to the caller
	return n * factorial(n - 1);
}
// Program execution starts in main()
int main() {
	// Print formatted text to the screen
	printf("%d", factorial(4));
	// Return 0 to signal that the program finished successfully
	return 0;
}

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson C Function Prototypes Next Lesson → C Scope & Lifetime