Recursion in C Language - Types, Advantages and Disadvantages with Examples रिकर्सन

What is Recursion in C Language?

Recursion is a programming technique in which a function calls itself directly or indirectly to solve a problem. The recursive calls continue until a terminating condition, also known as the base case, is reached. Recursion is useful for solving problems such as calculating the factorial of a number, generating Fibonacci series, and solving the Tower of Hanoi problem.

रिकर्सन एक प्रोग्रामिंग तकनीक है जिसमें कोई फंक्शन किसी समस्या को हल करने के लिए स्वयं को प्रत्यक्ष या अप्रत्यक्ष रूप से कॉल करता है। रिकर्सिव कॉल तब तक जारी रहती हैं जब तक टर्मिनेटिंग कंडीशन, जिसे बेस केस भी कहा जाता है, प्राप्त नहीं हो जाती। रिकर्सन का उपयोग किसी संख्या का फैक्टोरियल निकालने, फिबोनाची सीरीज बनाने तथा टावर ऑफ हनोई जैसी समस्याओं को हल करने में किया जाता है।

Rules of Recursion

A successful recursive function generally requires the following two important components:

एक सफल रिकर्सिव फंक्शन में सामान्यतः निम्नलिखित दो महत्वपूर्ण घटक होना आवश्यक है:

1. Base Case (Terminating Condition): A base case is a condition that stops further recursive calls. Every recursive function should have a reachable base case; otherwise, recursive calls may continue until the program runs out of stack memory.

बेस केस (टर्मिनेटिंग कंडीशन): बेस केस वह कंडीशन होती है जो आगे होने वाली रिकर्सिव कॉल को रोकती है। प्रत्येक रिकर्सिव फंक्शन में एक ऐसा बेस केस होना चाहिए जिस तक प्रोग्राम पहुँच सके। अन्यथा रिकर्सिव कॉल तब तक जारी रह सकती हैं जब तक प्रोग्राम की स्टैक मेमोरी समाप्त न हो जाए।

2. Recursive Case (Recursive Call): A recursive case contains one or more statements in which a function calls itself, either directly or through another function. Each recursive call should move the problem closer to the base case.

रिकर्सिव केस (रिकर्सिव कॉल): रिकर्सिव केस में एक या अधिक ऐसे स्टेटमेंट होते हैं जिनमें कोई फंक्शन स्वयं को प्रत्यक्ष रूप से या किसी दूसरे फंक्शन के माध्यम से कॉल करता है। प्रत्येक रिकर्सिव कॉल समस्या को बेस केस के और करीब ले जानी चाहिए।

Syntax of Recursion in C

return_type function_name(parameters)
{
    if (base_condition)
    {
        return value;
    }
    else
    {
        return function_name(arguments);
    }
}
int main(void)
{
    function_name(arguments);
    return 0;
}

In the above syntax, the function calls itself until the base condition becomes true. The function then returns the result to the previous function call.

उपरोक्त सिंटैक्स में फंक्शन स्वयं को तब तक कॉल करता है जब तक बेस कंडीशन सत्य नहीं हो जाती। इसके बाद फंक्शन अपना परिणाम पिछली फंक्शन कॉल को वापस करता है।

Example: Factorial of a Number Using Recursion

The factorial of a non-negative integer is the product of all positive integers from 1 to that number. The factorial of 0 is 1.

किसी गैर-ऋणात्मक पूर्णांक का फैक्टोरियल उस संख्या से लेकर 1 तक की सभी धनात्मक पूर्णांकों का गुणनफल होता है। शून्य का फैक्टोरियल 1 होता है।

Formula:

n! = n × (n-1)!
0! = 1

C Program:

#include <stdio.h>
unsigned long long factorial(unsigned int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}
int main(void)
{
    long long n;
    printf("Enter a number (0 to 20): ");
    if (scanf("%lld", &n) != 1 || n < 0 || n > 20)
    {
        printf("Invalid input. Enter a number from 0 to 20.");
        return 1;
    }
    printf("Factorial of %lld = %llu\n",
           n, factorial((unsigned int)n));
    return 0;
}

Output:

Enter a number (0 to 20): 5
Factorial of 5 = 120

Explanation: The factorial() function calls itself with a smaller value of n. When n becomes 0, the base condition becomes true and the function returns 1. The pending multiplication operations are then completed in reverse order. The program restricts input to 0–20 because larger factorial values may exceed the capacity of unsigned long long.

factorial() फंक्शन स्वयं को n से छोटी संख्या के साथ कॉल करता है। जब n का मान 0 हो जाता है, तब बेस कंडीशन सत्य हो जाती है और फंक्शन 1 वापस करता है। इसके बाद पहले से लंबित गुणा की सभी क्रियाएँ उल्टे क्रम में पूरी होती हैं। प्रोग्राम में इनपुट की सीमा 0 से 20 रखी गई है क्योंकि इससे बड़ी संख्याओं का फैक्टोरियल unsigned long long की क्षमता से अधिक हो सकता है।

Working of Recursion: Winding and Unwinding Process

The execution of recursion can be understood through two stages: winding and unwinding. During the winding process, recursive function calls are made and stored on the function call stack. During the unwinding process, the function calls return their results in reverse order.

रिकर्सन की कार्यप्रणाली को दो चरणों में समझा जा सकता है: वाइंडिंग और अनवाइंडिंग। वाइंडिंग प्रक्रिया में रिकर्सिव फंक्शन कॉल होती हैं और वे फंक्शन कॉल स्टैक में सुरक्षित रहती हैं। अनवाइंडिंग प्रक्रिया में फंक्शन कॉल उल्टे क्रम में अपने परिणाम वापस करती हैं।

1. Winding Process: Suppose we calculate factorial of 5. The function keeps calling itself with decreasing values until it reaches the base case.

वाइंडिंग प्रक्रिया: मान लीजिए हमें 5 का फैक्टोरियल निकालना है। फंक्शन घटते हुए मानों के साथ स्वयं को कॉल करता रहता है, जब तक कि वह बेस केस तक नहीं पहुँच जाता।

Function Call	Operation
factorial(5)	5 × factorial(4)
factorial(4)	4 × factorial(3)
factorial(3)	3 × factorial(2)
factorial(2)	2 × factorial(1)
factorial(1)	1 × factorial(0)
factorial(0)	Returns 1 (Base Case)

2. Unwinding Process: After reaching the base case, the function starts returning values to the previous calls and completes the pending multiplication operations.

अनवाइंडिंग प्रक्रिया: बेस केस तक पहुँचने के बाद फंक्शन पिछली कॉल को मान वापस करना शुरू करता है और पहले से लंबित गुणा की क्रियाएँ पूरी करता है।

Function Return	Operation
factorial(0)	1
factorial(1)	1 × 1 = 1
factorial(2)	2 × 1 = 2
factorial(3)	3 × 2 = 6
factorial(4)	4 × 6 = 24
factorial(5)	5 × 24 = 120

Therefore, the factorial of 5 is 120.

इस प्रकार, 5 का फैक्टोरियल 120 होता है।

Types of Recursion in C Language

Recursion can be classified in different ways depending on how recursive calls are made and how many recursive calls occur in a function.

रिकर्सिव कॉल किस प्रकार की जाती हैं और किसी फंक्शन में कितनी रिकर्सिव कॉल होती हैं, इसके आधार पर रिकर्सन को विभिन्न प्रकारों में बाँटा जा सकता है।

1. Tail Recursion

When a recursive call is the last operation performed by a function and no further computation is required after that call returns, it is called tail recursion.

जब किसी फंक्शन में रिकर्सिव कॉल अंतिम ऑपरेशन होती है और उसके वापस आने के बाद कोई अन्य गणना नहीं करनी पड़ती, तब उसे टेल रिकर्सन कहा जाता है।

Example:

void display(int n)
{
    if (n == 0)
        return;
    printf("%d ", n);
    display(n - 1);
}

In this example, the recursive call display(n - 1) is the last operation in the function. Therefore, it is an example of tail recursion.

इस उदाहरण में display(n - 1) रिकर्सिव कॉल फंक्शन का अंतिम ऑपरेशन है। इसलिए यह टेल रिकर्सन का उदाहरण है।

2. Non-Tail Recursion

When a recursive call is followed by one or more operations that must be performed after the recursive call returns, it is called non-tail recursion.

जब किसी फंक्शन में रिकर्सिव कॉल के बाद एक या अधिक ऐसे ऑपरेशन शेष रहते हैं जिन्हें रिकर्सिव कॉल के वापस आने के बाद पूरा करना होता है, तब उसे नॉन-टेल रिकर्सन कहा जाता है।

Example:

int factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

In this example, multiplication is performed after the recursive call returns. Therefore, it is an example of non-tail recursion.

इस उदाहरण में रिकर्सिव कॉल के वापस आने के बाद गुणा की क्रिया पूरी होती है। इसलिए यह नॉन-टेल रिकर्सन का उदाहरण है।

3. Direct Recursion

When a function calls itself directly, it is called direct recursion.

जब कोई फंक्शन स्वयं को सीधे कॉल करता है, तब उसे डायरेक्ट रिकर्सन कहा जाता है।

Example:

void display(int n)
{
    if (n == 0)
        return;
    printf("%d ", n);
    display(n - 1);
}

Here, the display() function directly calls itself. Therefore, it is an example of direct recursion.

यहाँ display() फंक्शन स्वयं को सीधे कॉल करता है। इसलिए यह डायरेक्ट रिकर्सन का उदाहरण है।

4. Indirect Recursion

When one function calls another function and the second function calls the first function again, it is called indirect recursion. It involves two or more functions calling one another in a recursive sequence.

जब एक फंक्शन दूसरे फंक्शन को कॉल करता है और दूसरा फंक्शन पुनः पहले फंक्शन को कॉल करता है, तब उसे इनडायरेक्ट रिकर्सन कहा जाता है। इसमें दो या दो से अधिक फंक्शन एक-दूसरे को क्रमशः कॉल करते हैं।

Example:

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

Output:

5 4 3 2 1

Here, function1() calls function2(), and function2() calls function1(). Therefore, it is an example of indirect recursion.

यहाँ function1(), function2() को कॉल करता है तथा function2(), function1() को कॉल करता है। इसलिए यह इनडायरेक्ट रिकर्सन का उदाहरण है।

5. Simple Recursion (Linear Recursion)

In simple or linear recursion, a function makes only one recursive call during each activation of that function. The recursive calls generally form a single sequence.

सिंपल या लीनियर रिकर्सन में किसी फंक्शन के प्रत्येक निष्पादन के दौरान केवल एक रिकर्सिव कॉल होती है। इसमें रिकर्सिव कॉल सामान्यतः एक ही क्रम में आगे बढ़ती हैं।

Example:

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

In this example, the sum() function makes only one recursive call in each activation. Therefore, it is an example of linear recursion.

इस उदाहरण में sum() फंक्शन के प्रत्येक निष्पादन में केवल एक रिकर्सिव कॉल होती है। इसलिए यह लीनियर रिकर्सन का उदाहरण है।

6. Tree Recursion

When a function makes more than one recursive call during a single activation, it is called tree recursion. Its recursive calls form a branching structure similar to a tree.

जब किसी फंक्शन के एक निष्पादन के दौरान एक से अधिक रिकर्सिव कॉल होती हैं, तब उसे ट्री रिकर्सन कहा जाता है। इसमें रिकर्सिव कॉल एक पेड़ जैसी शाखाओं वाली संरचना बनाती हैं।

Example:

int fibonacci(int n)
{
    if (n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Here, the fibonacci() function makes two recursive calls: fibonacci(n - 1) and fibonacci(n - 2). Therefore, it is an example of tree recursion.

यहाँ fibonacci() फंक्शन दो रिकर्सिव कॉल करता है: fibonacci(n - 1) और fibonacci(n - 2)। इसलिए यह ट्री रिकर्सन का उदाहरण है।

The classifications of recursion are not mutually exclusive. For example, a function may use direct recursion as well as tail or non-tail recursion. Simple/linear and tree recursion describe the number of recursive calls made during each function activation.

रिकर्सन के ये प्रकार एक-दूसरे से पूरी तरह अलग नहीं हैं। उदाहरण के लिए, कोई फंक्शन डायरेक्ट रिकर्सन के साथ-साथ टेल या नॉन-टेल रिकर्सन भी हो सकता है। सिंपल/लीनियर और ट्री रिकर्सन किसी फंक्शन के एक निष्पादन में होने वाली रिकर्सिव कॉल की संख्या को दर्शाते हैं।

Advantages of Recursion

Recursion offers several advantages when solving problems that can naturally be divided into smaller subproblems.

रिकर्सन उन समस्याओं को हल करने में कई लाभ प्रदान करता है जिन्हें स्वाभाविक रूप से छोटी-छोटी समस्याओं में विभाजित किया जा सकता है।

1. Simple and Readable Code: Recursion can make programs shorter, cleaner and easier to understand for certain problems.

   सरल एवं पठनीय कोड: कुछ समस्याओं के लिए रिकर्सन प्रोग्राम को छोटा, स्पष्ट तथा समझने में आसान बना सकता है।

2. Suitable for Complex Problems: Problems such as Tower of Hanoi, tree traversal and divide-and-conquer algorithms can be expressed naturally using recursion.

   जटिल समस्याओं के लिए उपयोगी: टावर ऑफ हनोई, ट्री ट्रैवर्सल तथा डिवाइड एंड कॉन्कर एल्गोरिथम जैसी समस्याओं को रिकर्सन की सहायता से आसानी से व्यक्त किया जा सकता है।

3. Reduces Code Complexity: Recursive solutions may require fewer statements than their iterative alternatives.

   कोड की जटिलता कम करता है: रिकर्सिव समाधान में कभी-कभी इटरेटिव समाधान की तुलना में कम स्टेटमेंट लिखने पड़ते हैं।

4. Natural Problem Representation: Recursion is useful when a problem has a recursive structure, where a larger problem can be solved using smaller versions of the same problem.

   समस्या को स्वाभाविक रूप से प्रस्तुत करना: जब किसी बड़ी समस्या को उसी समस्या के छोटे रूपों की सहायता से हल किया जा सकता है, तब रिकर्सन उपयोगी होता है।

Disadvantages of Recursion

Although recursion is useful, it also has some limitations, particularly when it involves a large number of recursive calls.

हालाँकि रिकर्सन उपयोगी है, लेकिन इसकी कुछ सीमाएँ भी हैं, विशेषकर तब जब इसमें बहुत अधिक रिकर्सिव कॉल होती हैं।

1. More Memory Usage: Every recursive call requires additional stack memory to store function parameters, local variables and return information.

   अधिक मेमोरी का उपयोग: प्रत्येक रिकर्सिव कॉल में फंक्शन के पैरामीटर, लोकल वेरिएबल तथा रिटर्न संबंधी जानकारी सुरक्षित रखने के लिए अतिरिक्त स्टैक मेमोरी की आवश्यकता होती है।

2. Slower Execution in Some Cases: Recursive solutions may be slower than iterative solutions because of repeated function-call overhead.

   कुछ स्थितियों में धीमी गति: बार-बार फंक्शन कॉल होने के कारण रिकर्सिव प्रोग्राम कुछ स्थितियों में इटरेटिव प्रोग्राम की तुलना में धीमे हो सकते हैं।

3. Stack Overflow: If recursion becomes too deep or does not reach its base case, the program may exhaust the available call stack and cause a stack overflow.

   स्टैक ओवरफ्लो: यदि रिकर्सन बहुत गहरा हो जाए या बेस केस तक न पहुँचे, तो प्रोग्राम की उपलब्ध कॉल स्टैक मेमोरी समाप्त हो सकती है और स्टैक ओवरफ्लो की समस्या उत्पन्न हो सकती है।

4. Difficult to Debug: Understanding the sequence of recursive calls and return operations may be difficult for beginners.

   डिबग करना कठिन: रिकर्सिव कॉल तथा उनके रिटर्न होने के क्रम को समझना शुरुआती विद्यार्थियों के लिए कठिन हो सकता है।

5. Repeated Calculations: Some recursive algorithms, such as the simple recursive Fibonacci program, perform the same calculations repeatedly and may take a long time for larger inputs.

   बार-बार गणना: कुछ रिकर्सिव एल्गोरिथम, जैसे साधारण रिकर्सिव फिबोनाची प्रोग्राम, एक ही गणना को बार-बार करते हैं और बड़ी इनपुट वैल्यू के लिए अधिक समय ले सकते हैं।

Difference Between Recursion and Iteration

Recursion and iteration are two different techniques used to repeat a set of operations. Recursion uses function calls, whereas iteration uses loops such as for, while and do-while.

रिकर्सन तथा इटरेशन किसी कार्य को बार-बार करने की दो अलग-अलग तकनीकें हैं। रिकर्सन में फंक्शन कॉल का उपयोग होता है, जबकि इटरेशन में for, while तथा do-while जैसे लूप का उपयोग किया जाता है।

Recursion	Iteration
Uses recursive function calls.	Uses loops.
Requires call stack memory for each active call.	Usually requires less additional memory.
May be slower due to function-call overhead.	Often faster for simple repetitive tasks.
Must have a reachable base case.	Must have a suitable loop termination condition.
Useful for trees and recursive problems.	Useful for repetitive calculations and sequential processing.

रिकर्सन	इटरेशन
रिकर्सिव फंक्शन कॉल का उपयोग करता है।	लूप का उपयोग करता है।
प्रत्येक सक्रिय कॉल के लिए कॉल स्टैक मेमोरी की आवश्यकता होती है।	सामान्यतः कम अतिरिक्त मेमोरी की आवश्यकता होती है।
फंक्शन कॉल के कारण धीमा हो सकता है।	साधारण दोहराए जाने वाले कार्यों में अक्सर तेज होता है।
इसमें पहुँच योग्य बेस केस होना चाहिए।	इसमें लूप समाप्त करने की उचित कंडीशन होनी चाहिए।
ट्री तथा रिकर्सिव समस्याओं के लिए उपयोगी है।	बार-बार होने वाली गणनाओं तथा क्रमिक प्रोसेसिंग के लिए उपयोगी है।

Recursion is an important programming technique in C language. It makes many problems easier to express by dividing them into smaller subproblems. However, programmers should use recursion carefully because it can consume additional stack memory and may cause performance problems for certain algorithms. The choice between recursion and iteration depends on the nature of the problem.

रिकर्सन C लैंग्वेज की एक महत्वपूर्ण प्रोग्रामिंग तकनीक है। यह कई समस्याओं को छोटी-छोटी समस्याओं में विभाजित करके हल करना आसान बनाती है। हालाँकि, प्रोग्रामर को रिकर्सन का उपयोग सावधानीपूर्वक करना चाहिए क्योंकि इसमें अतिरिक्त स्टैक मेमोरी का उपयोग हो सकता है तथा कुछ एल्गोरिथम में परफॉर्मेंस संबंधी समस्याएँ आ सकती हैं। रिकर्सन और इटरेशन में से किसका उपयोग करना है, यह समस्या की प्रकृति पर निर्भर करता है।