Recursion and Recursive Function

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 को समझने का एक अच्छा उदाहरण है |

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 में 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 = जाता है |

एक बार फिर से 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 करना कहते हैं |

 

Program

#include<stdio.h>
main()
{
   printf(“\t Shadab”);
   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 में रखता है | इस तरह अब Stack में क्रमशः 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 से होता है

अब तीसरा Factorial 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 का प्रयोग करके बनाये जाते हैं | Recursive Function को Use करने के कुछ फायेदे निम्नानुसार हैं :

1 Recursive Function Non – Recursive Functions की तुलना में लिखने व समझने में सरल , char व छोटे होते हैं |

2 Program Directly किसी भी Problem के Solution का सिद्धांत Reflect कर देता है , कि किस प्रकार से किसी समस्या को Solve किया गया है |

3 इस प्रकार से Create किये गए Software को Maintain करना सरल होता है |

4 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 द्वारा भेजा जाता है |