इससे पहले वाले tutorial में हमने functions के बारे में लगभग सब कुछ पढ़ और समझ लिया था. इस tutorial में हम recursive function यानी recursion के बारे में बात करेंगे.
जब मैंने programming सीखना शुरू किया था तो मुझे recursion को समझना dinosaur की तरह बड़ा मुश्किल लगता था लेकिन जब समझ आ गया तो ant की तरह बहुत आसान लगने लगा.
ज्यादातर ये होता है की हम एक function में से दूसरे function को call करते हैं लेकिन जब आप किसी function में से उसी function को call करते हो तो उसे हम recursion कहते हैं और उस function को हम recursive function कहते हैं.
जब हमें अपने program में किसी problem को solve करने के लिए कुछ statements को तब तक execute करना हो जब तक हमें हमारा result नहीं मिल जाता और इस तरह के काम के लिए हम Iteration (loops) या recursion का use करते करते हैं.
कुछ-कुछ problem में आपको iteration और recursion एक जैसा लग सकता है लेकिन बड़ी-बड़ी complex problem में recursion का use iteration (loops) के use से ज्यादा आसान और छोटा हो जाता है.
C Programming में Function कैसे काम करता है?
अब क्योंकि recursion भी function process है इसलिए recursion समझने के लिए पहले आपको ये समझना होगा की C programming में function internally कैसे काम करता है.
जब आप अपने C program में किसी function को call करते हो तब उस function को आपकी computer की stack memory में space allocate किया जाता है.
जब तक उस function के statements execute होते रहेंगे तब तक वो function और उसके local variable stack memory में मौजूद रहेंगे और जैसे ही function execution पूरा हो जाएगा वैसे ही stack memory में उस function और उसके सभी variables को हटा दिया जाएगा.
अगर आप किसी एक function को एक से ज्यादा बार call करते हो तो हर function call पर stack memory में उस function को बार-बार अलग-अलग space allocate किया जाएगा.
जैसा की आप ऊपर image में देख सकते हो हमने function को 2 बार call किया है जिसकी वजह से function को stack memory में 2 बार अलग-अलग space allocate किया गया है.
अगर first call वाले function में कोई changes होगा तो उसका effect दूसरे function में नहीं पड़ेगा. आइए इस बात को example के साथ समझते हैं.
#include <stdio.h>
void hmt();
int main()
{
hmt();
hmt();
hmt();
return 0;
}
void hmt()
{
int x=10;
printf("%d ",x);
x++;
}
जब मैं students से ये पूछता हूँ की ऊपर दिए गए program का output क्या आएगा तो उनमें से ज्यादातर students का answer होता है 10 11 12 और शायद आपका output भी यही हो.
अगर आपका output भी 10 11 12 है तो आपको ये जानकर हैरानी होगी की ये output गलत है इसका सही output है 10 10 10 यानी तीनों बार function call होने पर variable x की value 10 ही print होगी.
जब हमने अपने main function में पहली बार hmt function call किया तो उसे stack memory में space allocate हुआ होगा.
Function में हमने variable x की value जो हमने 10 initialize की उसे print करवाकर उसकी value में increment किया है जिससे variable x की value 10 से 11 हो जाएगी.
लेकिन उसके तुरंत बाद function complete हो गया है जिसकी वजह से hmt function और उसके variable को memory से हटा लिया जाएगा और program का control फिर से main function में चला जाएगा.
अब जब आप main function में से दूसरी बार hmt function call करेंगे तो उस function को और उसके variable x को memory में बिलकुल नये तरह से space allocate किया जाएगा.
यानी variable x को फिर से value 10 से initialize किया जाएगा. अब अगर आप सोचो पहले तो variable x की value 11 हो गयी थी तो मैं आपको याद दिला दूँ वो पहली function call वाले function में हुआ था जिसे memory से हटा लिया गया है.
इसी तरह जब दूसरी function call की function definition पूरी हो जाएगा उसे भी memory से हटा लिया जाएगा और same process तीसरी function call के साथ होगा.
C Programming में Recursion कैसे काम करता है?
अगर आप किसी बड़ी programming problem को recursion की help से solve करते हो तो recursion उस बड़ी problem को छोटी-छोटी problems में divide करके solve करता है.
Recursive function खुद को बार-बार इस तरह से call करता है की एक बड़ी problem हर call पर छोटी problem में divide हो जाती है और फिर उस छोटी problem को solve कर दिया जाता है.
हम recursive function को इस तरह से code करते हैं की जब बड़ी problem पूरी तरह से solve हो जाए तो recursion process रुक जाए यानी function खुद को call करना बंद कर दें.
आइये अब एक examples के साथ समझते हैं की C programming में recursion कैसे काम काम करता है.
Print First N Natural Numbers in Reverse using Recursion
#include <stdio.h>
void myprint(int num);
int main()
{
int n;
printf("Enter a Number : ");
scanf("%d",&n);
myprint(n);
return 0;
}
void myprint(int num)
{
printf("%d ",num);
if(num==1)
{
return;
}
else
{
myprint(num-1);
}
}
Output:
5 4 3 2 1
Explanation:
नीचे image में मैंने image illustration की help से ये समझाया की ऊपर वाले program में recursive function stack memory में internally कैसे काम करेगा.
जैसा की आप पहले पढ़ चुके हैं की main function को system द्वारा अपने आप call किया जाता है यानी stack memory में सबसे पहले main function को space allocate किया जाता है.
Step 1: main function में से हमने myprint function को call किया है. myprint function call होते है उसे भी stack memory में space allocate हो जाएगा.
function calling के समय हमने agrument के तौर पर value 5 को pass किया है जो myprint function के variable num में store हो जाएगी.
इसके बाद हमने variable num को print कराया है और उसके बाद if statement की condition (5==1) false हो जाएगी जिसकी वजह से program का control else में चला जाएगा.
Step 2: else में से myprint function फिर से खुद को call करेगा और यानी memory में फिर से अलग myprint function को space allocate किया जाएगा.
function calling के समय हमने agrument के तौर पर value 4 को pass किया है जो myprint function के variable num में store हो जाएगी.
इसके बाद हमने variable num को print कराया है और उसके बाद if statement की condition (4==1) false हो जाएगी जिसकी वजह से program का control else में चला जाएगा.
इसके बाद Step 3, Step 4 और Step 5 में step 2 की तरह ही लगभग same process होगा. बस Step 5 क्योंकि variable num की value 1 होगी इसलिए if condition true हो जाएगी.
जिसकी वजह से myprint function फिर से call नहीं होगा यानी recursive function call खत्म हो जाएगी और फिर एक-एक करके सभी functions execution reverse order में complete होती जाएगी.
जिसकी वजह से program का control उसके caller function की तरह वापस लोटेगा जो आपको image में Step 6, 7, 8, 9 और 10 में show हो रहा है. आइये reursion का एक और example समझ लेते हैं.
Find the Sum of First N Natural Numbers using Recursion:
#include <stdio.h>
int sum(int num);
int main()
{
int n,x;
printf("Enter a Number : ");
scanf("%d",&n);
x=sum(n);
printf("Sum of 1 to %d numbers : %d",n,x);
return 0;
}
int sum(int num)
{
if(num==1)
{
return 1;
}
else
{
return num + sum(num-1);
}
}
Output:
Enter a Number : 3 Sum of 1 to 3 numbers : 6
Explanation:
सबसे पहले हमने main function में से हमने sum function को call किया है. function calling के समय हमने agrument के तौर पर value 3 को pass किया है जो call किये गए sum function के variable num में store हो जाएगी.
Step 1: sum function के अंदर if statement की condition (3==1) false हो जाएगी जिसकी वजह से program का control else में चला जाएगा.
else में return statement लिखा जो value 3 को वहां return करेगा जहाँ से इस function को call किया गया है यानी main function पर लेकिन return statement अभी function को return कर नहीं पाएगा.
क्योंकि return statement को पूरा होने से पहले ही फिर से sum function call हो जाएगा और इस बार agrument के तौर पर value 2 को pass किया है जो call किये गए sum function के variable num में store हो जाएगी.
Step 2: इस step में भी लगभग step 1 की तरह ही process होगा यानी इसके भी else statement में return statement पूरा होने से पहले sum function फिर से call होगा.
इस बार agrument के तौर पर value 1 को pass किया है जो call किये गए sum function के variable num में store हो जाएगी.
Step 3: sum function के अंदर if statement की condition (1==1) true हो जाएगी और जिसकी वजह से sum function फिर से call नहीं होगा यानी recursive function call खत्म हो जाएगी.
यहाँ से value 1 वहां return होगी जहाँ से इस function को call किया गया है यानी step 2 पर और वहां पर returned value 1 value 2 (1+2) के साथ add हो जाएगी.
इसके बाद step 2 से value 3 वहां return होगी जहाँ से इस function को call किया गया है यानी step 1 पर और वहां पर returned value 3 value 3 (3+3) के साथ add हो जाएगी.
इसके बाद step 1 से value 6 वहां return होगी जहाँ से इस function को call किया गया है यानी main function पर और वहां पर returned value 6 variable x में store हो जाएगी जिसे हमने program में print कराया है.
Note: Recursive function में exit condition होना जरूरी होनी जिससे function खुद को call करना बंद कर दें.
What’s Next: इस tutorial में हमने Recursion Functions के बारे में पढ़ा. Next tutorial में हम C programming में Storage Classes का use करना सीखेंगे