Recursion concepts

📖 Theory

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

અત્યાર સુધી તમે લખેલું દરેક function બીજાં functions બોલાવે છે. આજનો વળાંક પહેલી વાર સાંભળતાં ગેરકાયદે લાગે છે:

fact(4) પોતાનો જવાબ... fact(3) બોલાવીને ગણે છે. જે fact(2) બોલાવે છે. જે fact(1) બોલાવે છે.

Function પોતાની જાતને બોલાવે છે. Students ને recursion કાં તો બહુ ગમે છે કાં તો એનો ડર લાગે છે, અને ફરક હંમેશા એક જ વાતનો હોય છે: એમણે એને એક વાર, ધીમેથી, હાથે અનુસર્યું છે કે નહીં. બરાબર એ જ આપણે કરીશું.

📖 Theory

હરોળમાં આગળ પૂછતાં જવું

તમે canteen ની હરોળમાં આઠમા છો અને તમારો ક્રમ જાણવો છે, પણ આગળનો છેડો દેખાતો નથી. એટલે તમે આગળની વ્યક્તિને પૂછો છો: "તમારો ક્રમ કયો?" એમને પણ ખબર નથી, એટલે એ આગળ પૂછે છે... જ્યાં સુધી પ્રશ્ન પહેલી વ્યક્તિ સુધી પહોંચે, જેને સીધી ખબર છે: "હું પહેલો છું."

હવે જવાબો પાછા વહે છે: પહેલો, એટલે બીજો, એટલે ત્રીજો... છેક તમારા સુધી: આઠમો. એક પ્રશ્ન આગળ પસાર થયો, પાછા વળતાં જવાબો બંધાયા. એ જ recursion છે, એની અટકાવનારી વ્યક્તિ સાથે.

📖 Theory

બે ફરજિયાત ભાગ

દરેક સાચા recursive function ને બરાબર બે ભાગ હોય છે:

• Base case: એટલું નાનું input કે function પોતાને બોલાવ્યા વગર સીધો જવાબ આપી દે. એ વ્યક્તિ જેને ખબર છે કે એ પહેલી છે.
• Recursive case: સમસ્યાને એક પગલું નાની કરો અને નાના ટુકડા પર પોતાની જાતને બોલાવો.

Factorial માટે (n! = n × (n-1) × ... × 1):

• Base: fact(1) = 1
• Recursive: fact(n) = n × fact(n-1)

Base case ન હોય, કે એવું પગલું હોય જે એની તરફ ક્યારેય ઘટતું જ ન હોય, તો calls ક્યારેય અટકતા નથી.

⌨️ Practical

Factorial, પોતાના જ ઉલ્લેખની ચાર લીટી

#include <iostream>
using namespace std;

long fact(int n) {
    if (n <= 1)            // BASE CASE: answer directly
        return 1;
    return n * fact(n - 1); // RECURSIVE CASE: smaller problem
}

int main() {
    cout << fact(4) << endl;   // 24
    return 0;
}

📖 Theory

Call stack પરનો પ્રવાસ

Calls base case સુધી ઉપર ખડકાય છે, પછી પરિણામો નીચે પાછાં આવે છે:

fact(4)

fact(3)

fact(2)

fact(1) → 1 (base case reached)

2 × 1 → 2

3 × 2 → 6

4 × 6 → 24

દરેક બાકી રહેલો call call stack પર memory માં રાહ જુએ છે: fact(3) પાછું ન આવે ત્યાં સુધી fact(4) પૂરું થઈ શકતું નથી. નીચે જતાં push, પાછા વળતાં pop: stack ના પાઠનું LIFO, જે તમારા programs ને અંદરથી ચલાવે છે.

💭 Think first

એક જાતે અનુસરો

એ જ function વાપરીને, કાગળ પર fact(5) અનુસરો: base case સુધીના calls ની સાંકળ લખો, પછી પાછા વળતાં થતા ગુણાકાર. અંતિમ મૂલ્ય શું છે, અને કયો call પહેલો પૂરો થાય છે?

🧩 Quiz

એક student લખે છે: long fact(int n) { return n * fact(n - 1); } કોઈ if વગર. fact(4) ચાલે ત્યારે શું થાય છે?

1. Calls ક્યારેય અટકતા નથી, call stack ભરાઈ જાય છે, અને program તૂટી પડે છે (stack overflow)
2. એ તોય 24 પાછું આપે છે; base case મરજિયાત છે
3. Compile ની ભૂલ: recursion ને if નું વિધાન જોઈએ જ
4. એ 0 પાછું આપે છે કારણ કે આખરે fact(0) સુધી પહોંચાય છે

⚠️ Watch out

પરીક્ષાની ચોકસાઈ: recursion સામે iteration

જાણીતો 5 marks નો પ્રશ્ન ભેદ પૂછે છે. આનાથી marks મેળવો:

• Recursion: ટૂંકો code, પોતાના જેવી જ નાની નકલવાળી સમસ્યાઓ માટે સ્વાભાવિક (trees, Tower of Hanoi), પણ દરેક call stack ની memory અને call નો બોજ માંગે છે.
• Iteration (loops): ક્યારેક વધુ code, પણ stack વધતો નથી.
• દરેક recursion ને iteration તરીકે ફરી લખી શકાય; ઊલટું પણ સાચું છે.

અને recursion ની વ્યાખ્યા આપતી વખતે બે ભાગનાં નામ (base case, recursive case) આપવાનું ક્યારેય ન ભૂલો.

📖 Theory

Recursion ક્યાં સ્વાભાવિક ભાષા છે

Folders ની અંદર folders, બે પાઠ પછી આવતી tree ની રચનાઓ, પછીના semesters માં મળનારા quicksort અને mergesort, JSON નું વાચન: બધું પોતાના જેવી નકલવાળું, બધું સ્વાભાવિક રીતે recursive. જ્યારે સમસ્યાની અંદર જ પોતાની નાની નકલ હોય, ત્યારે recursion યુક્તિ નથી, એ પ્રામાણિક વર્ણન છે.

✅ Summary

Key takeaways

• Recursion: function નાના input પર પોતાની જાતને બોલાવે છે જ્યાં સુધી base case સીધો જવાબ ન આપે.
• બે ફરજિયાત ભાગ: base case (બ્રેક) અને recursive case (નાનું પગલું).
• fact(4): calls 4,3,2,1 ખડકાય છે અને પરિણામો ઊલટા ક્રમમાં પાછાં આવે છે: 1,2,6,24.
• દરેક બાકી રહેલો call call stack પર frame તરીકે વસે છે: નીચે જતાં push, પાછા વળતાં pop (LIFO).
• Base case ખૂટે = stack overflow થી તૂટવું, compile ની ભૂલ નહીં.
• Recursion ટૂંકા, પોતાના જેવા code માટે stack ની memory આપે છે; loops ઊલટો સોદો કરે છે.
• Memory hook: કોઈને ખબર પડે ત્યાં સુધી હરોળમાં આગળ પૂછતાં જવું.