Recursive Function in C – Explained with Factorial Program

Recursive Function in C: हम जिस प्रकार से 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 को समझने का एक अच्छा उदाहरण है।

//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 करना कहते हैं।

//Program
#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 में रखता है। इस तरह अब 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 का प्रयोग करके बनाते हैं वे सभी 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 करना बहुत ही भयानक काम बन जाता है।

Recursive Function Create करने के लिए जब हम किसी Function को  Call करते हैं, तो उस Function को मूलत: दो तरीकों से Call किया जा सकता है, जिन्‍हें Call by Value या Pass by Value तथा Call by Address या Pass by Address के नाम से जाना जाता है:

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

Buy this eBook for Complete Discussion about

Recursion and Recursive Functions in C