recursion

Function With Argument And Return Value
इस प्रकार के User Defined Function में Calling Function से User Defined Function को Argument भी Pass किये जाते हैं और User Defined Function से किसी प्रकार की प्रक्रिया करवा कर वापस मान भी प्राप्त किये जाते हैं। हम ऊपर के ही प्रोग्राम में थोडा सा बदलाव करके इसे Function with Argument and Return Value में बदल सकते हैं। देखें निम्न प्रोग्राम

view plainprint?
#include<stdio.h>
main()
{
    int j, k, c, d;
    clrscr();
     
    printf(“\n Enter fist and Second Value:”);
    scanf(“%d %d”, &j , &k);
     
    c = sum (j, k);
    printf(“\n Sum of %d and %d is %d”, j, k, c);
     
    d = mul (j, k);
    printf(“\n Multiplication of %d and %d is %d”, j, k, d);
     
    getch();
}
 
 
 
sum ( int x , int y)
{
    int z;
    z = x + y;
    Return (z );
}
 
mul (int l, int m )
{
    int n;
    n = l * m;
    Return ( n );
}

इस प्रोग्राम में दो अन्य Variable c व d को main() Function में Declare किया गया है। सारी प्रक्रिया पहले प्रोग्राम की तरह ही रहती है, लेकिन जब Program Control, User Defined Function  sum में पहुंचता है, तब j व k का Formal Argument x व y में जाता है और x व y के मानों का योग z में Store हो जाता है। Program Control को यहां Return Statement मिलता है, जो z का मान main() को Return कर देता है। इससे z में Store मान main() Function में Declared Variable c को Assign हो जाता है, क्योंकि c = sum (j, k) लिखा है। इससे मान Return होने के बाद c = z हो जाता है और Output में c को Print करवा दिया जाता है। फिर Program Control को d = mul ( j, k ); Statement प्राप्त होता है। Program Control, mul User Defined Function में जाता है। यहां main() Function के j व k का मान l व m को प्राप्त हो जाता है। इस Function में l व m के गुणनफल को n में Store किया जाता है और ये मान main() Function को Return कर दिया जाता है, जिससे d का मान n के मान के बराबर हो जाता है। अब Output मे d का मान Print कर दिया जाता है, जो कि j व k के Multiplication के बराबर है। इस प्रकार से हम किसी भी Function से User Defined Function में Argument प्राप्त करके पुनः Calling Function को मान Return कर सकते हैं।

Example :   ARGUMENT WITH RETURN VALUE
view plainprint?
// Prototype Declaration
void printline(char ch, int len);
value(float, float, int);
 
#include<stdio.h>
 
main()
{
    float principal, inrate, amount;
    int period;
    clrscr();
     
    printf("Enter the principal amount interest:");
    printf("rate and period:\n");
    scanf("%f %f %d", &principal, &inrate, &period);
     
    printline('*',52);
     
    amount=value(principal, inrate, period);
     
    printf("\n%f\t%f\t%d\t%f\n\n", principal, inrate, period, amount);
    printline('=',52);
    getch();
}
 
 
 
//Function :  
void printline(char ch, int len)
{
    int i;
    for(i=1;i<= len; i++)
    printf("%c", ch);
    printf("\n");
}
 
 
 
//Function :  
value(float p, float r, int n)
{
    int year;
    float sum;
    sum=p;
    year=1;
     
    while(year<=n)
    {
        sum=sum*(1+r);
        year=year+1;
    }
    return(sum);
}
 
 
 
//Output:
Enter the principal amount interest: rate and period:
4500
3
5
******************************************
4500.000000 3.000000 5 20480.000000
=====================================

4    Function Without Argument But Return Value
इस प्रकार के Function में हम Calling Function से कोई मान, User Defined Function में प्रदान नहीं करते हैं, लेकिन Calling Function को मान Return किया जाता है। इस तरह के Function व्यवहारिक तौर पर बहुत ही कम प्रयोग में आते हैं।

Example :   Factorial ज्ञात करने का प्रोग्राम Functionके प्रयोग से बनाइये।
view plainprint?
#include<stdio.h>
 
main()
{
    int a, b;
    clrscr();
     
    printf("enter the factorial value:");
    scanf("%d", &a);
     
    b=fact(a);
     
    printf("fact=%d", b);
    getch();
}
 
fact(int x)
{
    int i, sum=1;
    for(i=1;i<=x; i++)
    sum*=i;
    return(sum);
}
 
 
 
//Output:
    enter the factorial value:5
    fact=120

Recursion and Recursive Function
हम जिस प्रकार से User Defined Function को main() Function में Call करते हैं, उसी प्रकार से किसी भी अन्य Function को किसी भी User Defined Function में Call कर सकते हैं। यहां तक कि main() Function को भी किसी User Defined Function में Call कर सकते हैं, क्योंकि main() Function भी एक User Defined Function ही है, जिसे User अपनी आवश्‍यकता के अनुसार लिखता है। हम किसी Function को खुद उसी Function में Call कर सकते हैं। जब हम किसी Function को वापस उसी Function में Call करते हैं, तो ये एक प्रकार की Looping हो जाती है। इस प्रक्रिया को “C” में Recursion कहा जाता है और ऐसे Function को Recursive Function कहते हैं। इस प्रक्रिया में वह Function तब तक Execute होता रहता है, जब तक कि किसी Condition द्वारा उसे Terminate ना कर दिया जाए। Factorial ज्ञात करने में Recursive Function को Use किया जा सकता है। ये Recursive Function को समझने का एक अच्छा उदाहरण है।
view plainprint?
//Recursive Function :  
Factorial ( n )
int n;
{
    int fact;
     
    if ( n = = 1)
    return ( 1 );
    else
    fact = n * Factorial ( n –1 );
    return ( fact );
}
मानलो कि हमें संख्‍या 5 का Factorial ज्ञात करना है। मान 5 का Factorial ज्ञात करने के लिए हमें मान 5 को Factorial Function में Argument के रूप में भेजना होता है। ये Function स्वयं को 5 बार निम्नानुसार Recursively Call करता हैः

Factorial(n)   =  Factorial(5)
=  5 * Factorial(4)
=  5 * ( 4 * Factorial(3))
=  5 * ( 4 * ( 3 * Factorial(2)))
=  5 * ( 4 * ( 3 * ( 2 * Factorial(1))))
=  5 * ( 4 * ( 3 * ( 2 * ( 1 ))))
=  120

जब हम इस Function में संख्‍या 5 Argument के रूप में देते हैं तो सबसे पहले if Condition Check होती है कि क्या n का मान 1 है या नहीं। चूंकि अभी n का मान 5 है इसलिए if Condition False Return करता है और Program Control else Statement Block में जाता है। यहां पर वापस Factorial Function मिलता है लेकिन इस बार Factorial Function में Argument के रूप में 5-1 = 4 जाता है। वापस से Factorial Function Call होता है और if Condition में Check किया जाता है कि n का मान 1 है या नहीं। यहां पर वापस n का मान 4 होने से Condition False हो जाती है और else Statement Block Execute होता है। वापस से Factorial Function Call होता है और Argument के रूप में इस बार Function में 4-1 = 3 जाता है। एक बार फिर से Factorial Function में n का मान Check होता है। n का मान इस बार 3 है इसलिए वापस से else Statement Block Execute होता है जहां फिर से Factorial Function Call होता है और इस बार इस Function में Argument के रूप में 3-1 = 2 जाता है। फिर से if Condition False हो जाती है और else Statement Block Execute होता है और एक बार फिर से Factorial Function Call होता है। इस बार Argument के रूप में 2-1 = 1 जाता है। इस बार n का मान 1 होता है इसलिए if Condition True हो जाती है और Program Control इस Factorial Function से बाहर आ जाता है तथा Return Value के रूप में 1 Return करता है। Program Control अन्तिम Factorial से बाहर आते ही Second Last Factorial में पहुंचता है। यहां मान 1 का मान 2 से गुणा होता है। और परिणाम fact नाम के Variable में Store हो जाता है। अब ये Factorial Function fact के मान 2 को Return करता है। इस मान 2 का गुणा पिछले Factorial के मान 3 से होता है और वापस से परिणाम fact नाम के Variable में Store हो जाता है। ये मान वापस पिछले Factorial में Return होता है जहां पर Return होने वाले मान 6 का गुणा मान 4 से होकर Variable fact में Store हो जाता है। ये मान अन्तिम Factorial में Return होता है जहां मान 5 से इस Return होने वाले मान 24 का गुणा होता है। अब ये अन्तिम Factorial Function 120 Return करता है जो कि उस main() Function या Calling Function में Return होता है जिसमें इस Factorial Function को Call किया गया था और Argument के रूप में मान 5 भेजा गया था।

साधारण तरीके से देखें तो निम्न प्रोग्राम में main() Function को पुनः main() Function में Call किया गया है, जिससे Program Infinite हो जाता है। क्योंकि जैसे ही Program Control, Block के Statement को Execute करता है, उसे वापस main() Function मिल जाता है और Program को वापस main() को Execute करना पडता है। ये क्रम अनन्त तक चलता रहता है। जब एक Function में किसी अन्य Function को प्रयोग किया जाता है, तो इसे Function की Nesting करना कहते हैं।

view plainprint?
#include<stdio.h>
 
main()
{
    printf(“\t Govinda ”);
    main();
}

हमारा CPU हर समय किसी ना किसी Program के किसी ना किसी Statement व Data पर Processing कर रहा होता है। जब हम किसी Function को Call करते हैं तो हमारा CPU अपने पुराने काम को छोड कर नए काम को करता है। उदाहरण के लिए जब पहली बार Factorial Function Call होता है, तो Factorial Function के Call होने से पहले हमारा Program Main Function के Statements का Execution कर रहा होता है। Factorial Function के Call होते ही हमारा CPU जिस Data की Processing कर रहा होता है उस Data को और उस Data पर जिस प्रकार की Processing करनी है, उस Processing की Instructions को एक विशेष प्रकार की Memory में रख देता है, जिसे Stack कहते हैं। Stack एक ऐसी Memory होती है जिसका प्रयोग हमारा CPU अपने Data व Programs Instructions को कुछ समय के लिए Temporarily Store करने के लिए करता है।

मानलो कि हमने Factorial Function को main() Function में Call किया है। तो CPU Factorial Function को Call करने से पहले main() Function के Data को Stack में रख देता है। फिर Factorial Function को Call करता है और Argument के रूप में Calling Function से आने वाले मान को Hold करने के लिए Variable n Create करता है। जब Program Control आगे बढता है तो उसे वापस Factorial Function प्राप्त होता है। इस Factorial Function को Call करने से पहले Program Control अपने Current Data 5 को जो कि Variable n में पडा है, को Stack पर रखता है और फिर से Recursively Factorial Function को Call करता है साथ ही इस बार इसी Function में Argument के रूप में एक नया मान 4 प्रदान करता है। फिर से मान 4 को Hold करने के लिए एक Variable n Create करता है। Program आगे बढता है तो वापस उसे एक और Factorial Function मिलता है। इस Factorial को तीसरी बार Call करने से पहले वापस मान 4 को Stack पर रखता है। अब Stack में दो मान 5 व 4 होते हैं। फिर से Factorial Call होता है और Argument के रूप में आने वाले मान 3 को Hold करने के लिए एक Variable n Create करता है। Program फिर आगे बढता है और फिर से Factorial को Call करने से पहले मान 3 को Stack में रखता है। इस तरह अब ैजaबा में क्रमश: 5, 4, व 3 Stored रहते हैं। इसी तरह से दो बार और Factorial Function Call होता है और Stack में क्रमश: 5, 4, 3, 2 व 1 Store हो जाता है। अब Program Control अन्तिम Factorial से 1 Return करता है। इस 1 का गुणा Stack पर पडे हुए 1 से होता है। Program Control अब चौथे Factorial से 1*2 = 2 Return करता है जिसका गुणा Stack पर पडे हुए मान 3 से होता है। अब तीसरा थ्ंबजवतial Function 2*3 = 6 Return करता है जिसका गुणा Stack पर पडे हुए दूसरे Factorial के मान 4 से होता है। ये दूसरा Function पहले Factorial को 24 Return करता है जिसका गुणा पहले Factorial के Stack में पडे हुए मान 5 से होता है। अन्त में ये पहला Factorial Function Calling Function को मान 120 Return करता है। इस तरह से एक Recursive Function Call होता है और Recursively Result प्रदान करता है।

Recursive Function एक प्रकार की Looping प्रदान करता है। यानी हम जो भी Program Looping का प्रयोग करके बनाते हैं वे सभी Program Recursive Functions का प्रयोग करके बनाए जा सकते हैं। Recursive Function को Use करने के कुछ मुख्‍य फायदे निम्नानुसार हैं:

Recursive Functions Non – Recursive Functions की तुलना में लिखने व समझने में सरल, Clear व छोटे होते हैं।
Program Directly किसी भी Problem के Solution का सिद्धांत Reflect कर देता है, कि किस प्रकार से किसी समस्या को Solve किया गया है।
इस प्रकार से Create किए गए Software को Maintain करना सरल होता है।
Recursive Functions का प्रयोग Non – Linear Data Structures को Maintain व Handle करने के लिए बहुत ही उपयोगी होता है।
किसी Non – Linear Data Structure को Handle करने के लिए हम किसी भी अन्य प्रकार के Statements का प्रयोग नहीं कर सकते हैं। वहां केवल Recursive Functions ही पूरी सक्षमता व पूर्णता के साथ उपयोग में लाया जा सकता है।

हालांकि Recursive Functions लिखना व Maintain करना काफी सरल होता है लेकिन यदि थोडी सी असावधानी हो जाए और इस Function में कोई Bug हो जाए, तो उसे Debug करना बहुत की भयानक काम बन जाता है। किसी भी प्रोग्राम में Function दो प्रकार से Call किये जा सकते हैं:


1    Call By Value
जब Calling Function से Variable के मान की एक Copy Parameter के रूप में User Defined Function को प्रदान की जाती है, तब इस प्रकार के Function को Call By Value Function कहा जाता है।


2    Call By Address
जब Calling Function से Variable के मान के स्थान पर Called Function में Variable का Address Pass किया जाता है, तो ऐसा Called Function, Call By Reference Function कहलाता है। ध्यान रहे कि Address हमेंशा Pointer Variable द्वारा भेजा जाता है।