Recursive function

📖 Theory

જે function પોતાને ફોન કરે છે

અત્યાર સુધી દરેક function એ બીજાઓને call કર્યા. C કંઈક વિચિત્ર ને પરવાનગી આપે છે: એક function પોતાને call કરતું.

પહેલી પ્રતિક્રિયા, બરાબર જ: "એ તો હંમેશા loop કરતું રહેશે."

લગભગ. એક ગુમ ઘટક સાથે એ ખરેખર અરીસાઓનો અનંત hall છે, અને એ ઘટક સાથે એ આ subject ની સૌથી સુંદર ચાર lines બની જાય છે: factorial, એવા function થી compute થતું જે મોટા ભાગનું કામ પોતાની જ એક નાની copy પર ભરોસો કરીને કરાવે છે.

📖 Theory

કતારમાં આગળ પૂછવું

તમે એક લાંબી કતારમાં છેલ્લા છો અને તમારી position જાણવી છે. આગળના ને પૂછો: "તમારી position શું છે?" એમને પણ ખબર નથી, એટલે એ આગળ પૂછે છે... જ્યાં સુધી સવાલ પહેલા વ્યક્તિ સુધી પહોંચે, જે બસ જાણે છે: "હું number 1 છું" (base case). હવે જવાબ પાછળની તરફ વહે છે, દરેક વ્યક્તિ એક ઉમેરે છે, જ્યાં સુધી તમારો જવાબ આવી જાય. એક સવાલ નીચે મોકલ્યો, જવાબ ઉપર બનતા ગયા: આ જ recursion ની આખી machinery છે.

📖 Theory

Recursion, ઔપચારિક રીતે

એક recursive function ને બરાબર બે ભાગ જોઈએ:

• Base case: સૌથી નાનું input, સીધો જવાબ અપાય, કોઈ આગળ call નહીં. આ જ brake છે.
• Recursive case: problem ને એક નાના self દ્વારા ફરી કહેવાય.

Factorial (n! = n × (n-1) × ... × 1) સ્વાભાવિક રીતે ફરી કહેવાય છે: n! = n × (n-1)! અને 0! = 1:

int factorial(int n) {

if (n == 0) return 1; /* base case */

return n * factorial(n - 1); /* smaller self */

}

દરેક call એ base case ની તરફ વધવું જોઈએ, દર વખતે નાનું n, નહીંતર brake ક્યારેય પહોંચતું નથી.

⌨️ Practical

Factorial, recursive અને loop વાળું

#include <stdio.h>

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

int main() {
    int f = 1, i, n = 4;
    printf("Recursive: %d\n", factorial(4));

    for (i = 1; i <= n; i++) f = f * i;   /* the loop twin */
    printf("Loop     : %d\n", f);
    return 0;
}

This example runs in Gri-Learn on the web, where you can edit it and see the output.

💭 Think first

Stack ને trace કરો

factorial(4) ને કાગળ પર trace કરો: calls ની શૃંખલા નીચે જતી લખો, ચિહ્નિત કરો ક્યાં થોભે છે, પછી પાછા ઉપર આવતા પરિણામોને ગુણો. શું return થાય છે, અને કયા data structure એ થોભેલી calls ને પકડી?

🧩 Quiz

એક student base case ભૂંસી નાખે છે: int factorial(int n) { return n * factorial(n - 1); } અને factorial(4) call કરે છે. શું થાય છે?

1. Calls ક્યારેય થોભતી નથી; call stack overflow થાય છે અને program crash થઈ જાય છે
2. તોય 24 return કરે છે, C ને factorials ખબર છે
3. એક compile error: base cases ફરજિયાત syntax છે
4. તરત 0 return કરે છે

🧩 Quiz

Factorial, loop તરીકે અને recursion તરીકે, બંને રીતે કામ કરે છે. કયું statement એમની સાચી સરખામણી કરે છે?

1. બંને સાચાં છે; loop stacked calls થી બચે છે, recursion સ્વાભાવિક રીતે nested problems પર ચમકે છે
2. Recursion હંમેશા loops થી ઝડપી છે
3. Loops 3 થી ઉપર factorials compute કરી શકતા નથી
4. Recursion ક્યારેય વધારાની memory વાપરતું નથી

⚠️ Watch out

Marks ક્યાં કપાય છે

કોઈ base case નહીં, કે એવો જ્યાં calls ક્યારેય પહોંચતી નથી (factorial(n-1) સાથે n == 5 વાળો base, 4 પર call): બંને stack overflow માં પૂરા થાય છે, નાનું થવાની દિશા તપાસો. ખોટી base value: factorial(0) એ 1 return કરવું જોઈએ, 0 નહીં, એક ખોટો brake અને એની ઉપરનો દરેક જવાબ 0. બેદરકારીથી trace કરવું: exams નીચે-શૃંખલા અને ઉપર-ગુણાકાર બંને લખેલા માંગે છે; પાછા ફરવાની સફર છોડવાથી અડધા marks જાય છે.

📖 Theory

ક્લાસિક બીજું ઉદાહરણ

Fibonacci (દરેક number એ પાછલા બે નો સરવાળો: 0 1 1 2 3 5 8...) એ recursion નો બીજો exam સિતારો છે: fib(n) = fib(n-1) + fib(n-2), બે base cases સાથે (fib(0)=0, fib(1)=1). આજે રાત્રે એને લખો; fib(4) trace કરો. C માં એક lesson બાકી છે: struct, જ્યાં આપણા student ને આખરે name, marks અને grade એક જ record માં મળે છે, આખા subject નું ઇનામ.

✅ Summary

Key takeaways

• Recursion: એક function જે પોતાને નાના input પર call કરે છે.
• બે ફરજિયાત ભાગ: base case (brake) + recursive case (નાનું self).
• factorial: if (n == 0) return 1; return n * factorial(n - 1);
• થોભેલી calls call stack પર રાહ જુએ છે (LIFO); પરિણામ પાછા ફરતાં ગુણાય છે.
• કોઈ base case નહીં → stack overflow crash; base પહોંચવા લાયક અને સાચો હોવો જોઈએ.
• સીધી ગણતરી માટે loops; સ્વાભાવિક રીતે nested problems માટે recursion.
• યાદ રાખવાની યુક્તિ: કતારમાં આગળ પૂછો, જવાબ પાછા ઉપર આવે છે.