YOUR C LEARNING COMPANION

Kahan se padhein?

Learning path
C ki buniyadChapter 14 of 73

Recursion: alag calls ko follow karein

Stopping cases, progress, separate local state, returned results aur recursive design ki limits samjhein.

5 min readDevelopingC17 baseline
Offline reading
Is chapter mein9 sections

Function problem ka chhota part solve karne ke liye doosri call use kar sakta hai. New call same function ki ho toh design ko recursion kehte hain. Main idea separate calls ki sequence hai; har call ka apna pending work hai.

1. Chhote question se shuru karein

One se three tak integers add karne ke liye keh sakte hain: three plus one se two ki sum. Chhoti sum two plus one tak ki sum hai. Aakhir zero par pahunchte hain, jahan add karne ka work nahi bachta. Har answer previous call ko finish karne deta hai.

Method ke do parts hain. Base case question ka direct answer deta hai. Recursive case remaining problem chhoti karta hai. Yahan zero base case hai aur one subtract karna uski taraf progress hai. Sirf self-call likhne se termination establish nahi hoti.

2. First example ki limits rakhein

Complete C17 example deliberately zero se ten tak values leta hai. Largest sum 55 hai, isliye har intermediate addition minimum standard unsigned int range mein bhi fit hoti hai. Assertions test build mein demonstration contract check karti hain. Yeh untrusted input validation ka replacement nahi hain.

Complete C17 program
#include <assert.h>

/* Contract: n is at most 10. */
static unsigned triangle(unsigned n)
{
    assert(n <= 10U);
    if (n == 0U) return 0U;
    return n + triangle(n - 1U);
}

static unsigned triangle_loop(unsigned n)
{
    assert(n <= 10U);
    unsigned total = 0U;
    for (unsigned i = 1U; i <= n; ++i) total += i;
    return total;
}

int main(void)
{
    for (unsigned n = 0U; n <= 10U; ++n) {
        assert(triangle(n) == triangle_loop(n));
        assert(triangle(n) == n * (n + 1U) / 2U);
    }
    return 0;
}

3. Calls neeche aur answers upar follow karein

CallResult ka wait karti calculationAakhir mein return
triangle(3)3 + triangle(2)6
triangle(2)2 + triangle(1)3
triangle(1)1 + triangle(0)1
triangle(0)—0

triangle(3) apna addition triangle(2) ke return hone ke baad finish karega. Woh triangle(1) ka aur woh triangle(0) ka wait karta hai. Zero pehle return hota hai. Phir pending additions one, three aur six deti hain. Ek call se return hone par caller resume hota hai; whole program restart nahi hota.

Visual model ke saath samjhein

Recursive calls aur returns follow karein

VISUAL MODEL

Small input choose karke triangle(n) follow karein. Dekhein kaunsi call wait karti hai aur kis result se caller aage badhta hai.

triangle 1 se n tak unsigned integers add karta hai. Har invocation ka apna n parameter hai.

  1. if (n == 0U) return 0U;
  2. return n + triangle(n - 1U);
Abhi chal rahi calls

Abhi koi call in progress nahi hai.

Final resultAbhi result return nahi hua

triangle(3) call karne ke liye tayyar hain. Abhi koi call shuru nahi hui.

Input 0–5 tak hai aur har sum unsigned int mein fit hai. Yeh source-level calls ka model hai; storage layout aur call optimisation implementation details hain.

Poora trace padhein
  1. triangle(3) call karne ke liye tayyar hain. Abhi koi call shuru nahi hui.
  2. triangle(3) mein enter karein. Is call ki apni parameter value 3 hai.
  3. triangle(2) mein enter karein. Is call ki apni parameter value 2 hai.
  4. triangle(1) mein enter karein. Is call ki apni parameter value 1 hai.
  5. triangle(0) mein enter karein. Is call ki apni parameter value 0 hai.
  6. triangle(0) stopping case par 0 return karta hai. Chhoti call ki need nahi.
  7. triangle(0) ne 0 return kiya. Caller triangle(1) ab 1 + 0 calculate karke 1 return kar sakta hai.
  8. triangle(1) ne 1 return kiya. Caller triangle(2) ab 2 + 1 calculate karke 3 return kar sakta hai.
  9. triangle(2) ne 3 return kiya. Caller triangle(3) ab 3 + 3 calculate karke 6 return kar sakta hai.
  10. Saari calls finish hain. triangle(3) ne original caller ko 6 return kiya.

4. Har call ki ordinary local state alag hai

Har invocation ko parameter ki apni value milti hai. Deeper calls caller ke n ko overwrite nahi karti. Recursive entries par ordinary automatic local objects ki separate instances hoti hain. Static local object storage-duration rules ke according calls mein shared hota. Counter ya cached result add karte waqt yeh difference important hai.

Unfinished worksheets ka stack useful mental model hai: newest question finish karke answer previous question mein use karein. Real implementations commonly call stack use karti hain. C exact physical arrangement, per-call fixed size ya unlimited recursion depth require nahi karti.

5. Structure useful ho tab recursion choose karein

Tree walk jaise smaller subproblems wale tasks mein recursion fit hoti hai. Simple linear sum loop mein clearer ho sakti hai; comparison ke liye dono forms upar hain. Functions indirectly ek-doosre ko call karke bhi recursion kar sakti hain. Progress, valid inputs aur depth policy ki need same hai.

Stopping case akela arithmetic overflow ya excessive work nahi rokta. Recursive Fibonacci same subproblems bahut baar repeat kar sakta hai. Tail-position call compiler se call storage remove karne ka portable promise nahi hai. Correctness, resource use aur implementation observations alag explain karein.

Sochkar dekhein

Function unchanged input se khud ko call kare, toh kya base-case branch hona finishing guarantee karta hai?

Explanation padhein

Nahi. Calls ko stopping case ya doosre justified exit tak pahunchna chahiye. Unchanged non-base input se same unfinished problem repeat hoti hai.

Primary references aur aage padhne ke links

Aage badhne se pehle

  • Recursive design ko stopping case aur uski taraf justified reduction chahiye.
  • Har invocation ke parameters aur ordinary automatic local instances alag hain.
  • Arithmetic range, call depth aur repeated work ki limits phir bhi chahiye.
In ideas ko alag rakhein
Calling downward / Returning upward
Smaller calls shuru hoti hain; unke results se waiting callers apna work finish karte hain.
Apne words mein samjhaayein

triangle(3) ko triangle(2) kyun chahiye, aur kis result se pehla waiting addition finish hota hai?

Optional: bolkar samjhein ya note rakhein. Tayyar hon toh aage badh sakte hain.

Apni understanding check karein

Optional hai. Answers save ya send nahi hote; chapter kabhi lock nahi hota.

Sirf base-case branch likhne se kya recursive calls finish hona guaranteed hai?
Har choice ki explanation padhein
  1. Haan, branch ki presence har call ko us tak pahunchati hai.

    Jo branch reach hi nahi hoti, woh recursion nahi rok sakti.

  2. Haan, C unlimited call depth guarantee karta hai.

    Resource use aur call depth ki unlimited portable guarantees nahi hain.

  3. Nahi. Calls ko stopping condition ki taraf justified progress aur resource limits chahiye.

    ✓ Sahi reasoning. Sound reasoning valid inputs, arithmetic, depth aur repeated work bhi consider karti hai.

C17

Agla idea padhne ke liye tayyar?

Mark this chapter as read whenever you feel ready.

CHAPTER 14 / 73

Is chapter mein

Recursion: alag calls ko follow karein

Search all 73 chapters in both languages.EN + HG

Try “pointer”, “why int”, or “undefined behavior”.

Concepts connect. Follow your curiosity.↑ ↓ to explore · Enter to open
MAKE YOURSELF COMFORTABLE

Your reading space

Appearance

A clear canvas with balanced contrast.

Text size

100%
AA

Reading tools

Your data stays in this browser

Export a backup before changing browsers or replacing an older version of the reader.

YOUR PERSONAL MARGINS

My notebook

Saved on this device
A LITTLE CLARITY

The glossary

A starting meaning, then a chapter to go deeper.

A QUICK DEFINITION

A little clarity

Read the full explanation →

A thought worth keeping