Recursion in C: Self-Calling Functions and Recursive Problem Solving
What is Recursion in C: Self-Calling Functions and Recursive Problem Solving? Here's a sentence that sounds like a riddle: a function that solves a problem by calling itself.That's recursion. It's a technique as old as mathematics — defin...
How do recursive functions invoke themselves, how does the call stack manage stack frames, and what prevents stack overflow?
Explanation & In-Depth Details
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="language-c bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;"><span class="js-id">int</span> <span class="js-id">countdown</span><span class="js-op">(</span><span class="js-id">int</span> <span class="js-id">n</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-kw">if</span> <span class="js-op">(</span><span class="js-id">n</span> <span class="js-op">==</span> <span class="js-num">0</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-cm">// ← BASE CASE: stop here printf("Liftoff!\n"); return 0; }</span>
<span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"%d... "</span><span class="js-op">,</span> <span class="js-id">n</span><span class="js-op">);</span> <span class="js-kw">return</span> <span class="js-id">countdown</span><span class="js-op">(</span><span class="js-id">n</span> <span class="js-op">-</span> <span class="js-num">1</span><span class="js-op">);</span> <span class="js-cm">// ← RECURSIVE CASE: smaller problem (n-1)}</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Call <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">countdown(3)</code> and you get:</p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="" data-language="" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;"><span class="js-num">3</span><span class="js-op">...</span> <span class="js-num">2</span><span class="js-op">...</span> <span class="js-num">1</span><span class="js-op">...</span> <span class="js-id">Liftoff</span><span class="js-op">!</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Read it as a sentence: <em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">"To count down from n: if n is 0, print Liftoff. Otherwise print n and count down from n-1."</em> That's the entire mental model.</p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">The critical detail is the shrinking.</span> <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">n - 1</code> is <em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">closer to the base case</em> than <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">n</code>. Every recursive call must move toward the stopping condition, or — like the infinite loops from our loops cluster — the recursion never ends. Just with a nastier failure mode (we'll get to that).</p><hr class="my-6" data-streamdown="horizontal-rule" style="border-width: 1px 0px 0px; border-style: solid; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); height: 0px; margin-block: 1rem 0.75rem; --tw-space-y-reverse: 0; font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><h2 class="mt-6 mb-2 font-semibold text-2xl" data-streamdown="heading-2" dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 22.5px 0px 7.5px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-size: 1.125rem; line-height: 1.35; --tw-space-y-reverse: 0; letter-spacing: -0.105469px; --tw-font-weight: 600; margin-block: 1.25rem 0.75rem; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; background-color: rgb(18, 18, 22);">How It Actually Works: The Call Stack</h2><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Here's the mechanism that makes recursion possible, and the part that makes it click for most people.</p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Every time a function is called, C creates a <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">new copy</span> of that function's local variables and stack frame and places it on the <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">call stack</span> — a stack of "suspended" work. When a function returns, its frame is popped off, and the previous one resumes.</p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">For <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">countdown(3)</code>, the stack grows like this:</p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="" data-language="" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;"><span class="js-id">countdown</span><span class="js-op">(</span><span class="js-num">3</span><span class="js-op">)</span> → <span class="js-id">prints</span> <span class="js-str">"3..."</span><span class="js-op">,</span> <span class="js-id">calls</span> <span class="js-id">countdown</span><span class="js-op">(</span><span class="js-num">2</span><span class="js-op">)</span> <span class="js-id">countdown</span><span class="js-op">(</span><span class="js-num">2</span><span class="js-op">)</span> → <span class="js-id">prints</span> <span class="js-str">"2..."</span><span class="js-op">,</span> <span class="js-id">calls</span> <span class="js-id">countdown</span><span class="js-op">(</span><span class="js-num">1</span><span class="js-op">)</span> <span class="js-id">countdown</span><span class="js-op">(</span><span class="js-num">1</span><span class="js-op">)</span> → <span class="js-id">prints</span> <span class="js-str">"1..."</span><span class="js-op">,</span> <span class="js-id">calls</span> <span class="js-id">countdown</span><span class="js-op">(</span><span class="js-num">0</span><span class="js-op">)</span> <span class="js-id">countdown</span><span class="js-op">(</span><span class="js-num">0</span><span class="js-op">)</span> → <span class="js-id">BASE</span> <span class="js-id">CASE</span><span class="js-op">:</span> <span class="js-id">prints</span> <span class="js-str">"Liftoff!"</span><span class="js-op">,</span> <span class="js-id">returns</span> <span class="js-num">0</span> ← <span class="js-id">countdown</span><span class="js-op">(</span><span class="js-num">1</span><span class="js-op">)</span> <span class="js-id">returns</span> ← <span class="js-id">countdown</span><span class="js-op">(</span><span class="js-num">2</span><span class="js-op">)</span> <span class="js-id">returns</span>← <span class="js-id">countdown</span><span class="js-op">(</span><span class="js-num">3</span><span class="js-op">)</span> <span class="js-id">returns</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Three separate <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">countdown</code> frames exist simultaneously, each with <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">its own <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">n</code></span> (3, 2, 1 respectively). They're not sharing a variable — they're independent copies. The recursion "unwinds" as each frame returns to the one below it.</p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">That's why base cases matter so much: <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">each unfinished call holds a stack frame in memory</span>. Never reaching a base case means creating frames forever — which is what produces the infamous <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">stack overflow</span> (the error, not the website). We'll cover that shortly.</p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">(Suggested image: the call-stack diagram with stacked frames, exactly as above, plus return arrows going back down. This is the single most important graphic on this page.)</em></p><hr class="my-6" data-streamdown="horizontal-rule" style="border-width: 1px 0px 0px; border-style: solid; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); height: 0px; margin-block: 1rem 0.75rem; --tw-space-y-reverse: 0; font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><h2 class="mt-6 mb-2 font-semibold text-2xl" data-streamdown="heading-2" dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 22.5px 0px 7.5px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-size: 1.125rem; line-height: 1.35; --tw-space-y-reverse: 0; letter-spacing: -0.105469px; --tw-font-weight: 600; margin-block: 1.25rem 0.75rem; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; background-color: rgb(18, 18, 22);">Example 1: Factorial — The Classic</h2><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Mathematically, <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">n! = n × (n-1) × ... × 1</code>, with the recursive definition:</p><ul class="list-inside list-disc whitespace-normal [li_&]:pl-6" data-streamdown="unordered-list" style="border: 0px solid rgb(47, 47, 55); margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); list-style: outside disc; padding-inline-start: 1.375rem; margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><li class="py-1 [&>p]:inline" data-streamdown="list-item" dir="ltr" style="border: 0px solid rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-block: 0.125rem;"><code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">0! = 1</code> (base case)</li><li class="py-1 [&>p]:inline" data-streamdown="list-item" dir="ltr" style="border: 0px solid rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-block: 0.125rem;"><code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">n! = n × (n-1)!</code> (recursive case)</li></ul><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">That definition <em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">is</em> the code:</p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="c" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="language-c" data-language="c" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="language-c bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;">#<span class="js-id">include</span> <span class="js-op"><</span><span class="js-id">stdio</span><span class="js-op">.</span><span class="js-id">h</span><span class="js-op">></span>
<span class="js-id">long</span> <span class="js-id">factorial</span><span class="js-op">(</span><span class="js-id">int</span> <span class="js-id">n</span><span class="js-op">);</span>
<span class="js-id">int</span> <span class="js-id">main</span><span class="js-op">()</span> <span class="js-op">{</span> <span class="js-id">int</span> <span class="js-id">num</span><span class="js-op">;</span>
<span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"Enter a number: "</span><span class="js-op">);</span> <span class="js-id">scanf</span><span class="js-op">(</span><span class="js-str">"%d"</span><span class="js-op">,</span> <span class="js-op">&</span><span class="js-id">num</span><span class="js-op">);</span>
<span class="js-kw">if</span> <span class="js-op">(</span><span class="js-id">num</span> <span class="js-op"><</span> <span class="js-num">0</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-id">puts</span><span class="js-op">(</span><span class="js-str">"Factorial is not defined for negative numbers."</span><span class="js-op">);</span> <span class="js-op">}</span> <span class="js-kw">else</span> <span class="js-op">{</span> <span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"%d! = %ld\n"</span><span class="js-op">,</span> <span class="js-id">num</span><span class="js-op">,</span> <span class="js-id">factorial</span><span class="js-op">(</span><span class="js-id">num</span><span class="js-op">));</span> <span class="js-op">}</span>
<span class="js-kw">return</span> <span class="js-num">0</span><span class="js-op">;}</span>
<span class="js-id">long</span> <span class="js-id">factorial</span><span class="js-op">(</span><span class="js-id">int</span> <span class="js-id">n</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-kw">if</span> <span class="js-op">(</span><span class="js-id">n</span> <span class="js-op">==</span> <span class="js-num">0</span> <span class="js-op">||</span> <span class="js-id">n</span> <span class="js-op">==</span> <span class="js-num">1</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-cm">// BASE CASE return 1; }</span>
<span class="js-kw">return</span> <span class="js-id">n</span> <span class="js-op">*</span> <span class="js-id">factorial</span><span class="js-op">(</span><span class="js-id">n</span> <span class="js-op">-</span> <span class="js-num">1</span><span class="js-op">);</span> <span class="js-cm">// RECURSIVE CASE}</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Sample Run:</span></p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="" data-language="" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;"><span class="js-id">Enter</span> <span class="js-id">a</span> <span class="js-id">number</span><span class="js-op">:</span> <span class="js-num">55</span><span class="js-op">!</span> <span class="js-op">=</span> <span class="js-num">120</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Trace for <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">factorial(5)</code></span> — follow the calls going down, then the multiplication coming back up:</p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="" data-language="" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;"><span class="js-id">factorial</span><span class="js-op">(</span><span class="js-num">5</span><span class="js-op">)</span> <span class="js-op">=</span> <span class="js-num">5</span> <span class="js-op">*</span> <span class="js-id">factorial</span><span class="js-op">(</span><span class="js-num">4</span><span class="js-op">)</span> <span class="js-num">4</span> <span class="js-op">*</span> <span class="js-id">factorial</span><span class="js-op">(</span><span class="js-num">3</span><span class="js-op">)</span> <span class="js-num">3</span> <span class="js-op">*</span> <span class="js-id">factorial</span><span class="js-op">(</span><span class="js-num">2</span><span class="js-op">)</span> <span class="js-num">2</span> <span class="js-op">*</span> <span class="js-id">factorial</span><span class="js-op">(</span><span class="js-num">1</span><span class="js-op">)</span> <span class="js-num">1</span> ← <span class="js-id">base</span> <span class="js-kw">case</span> <span class="js-id">returns</span> <span class="js-num">1</span>
<span class="js-id">Now</span> <span class="js-id">unwind</span> <span class="js-id">back</span> <span class="js-id">up</span><span class="js-op">:</span><span class="js-id">factorial</span><span class="js-op">(</span><span class="js-num">1</span><span class="js-op">)</span> <span class="js-op">=</span> 1factorial<span class="js-op">(</span><span class="js-num">2</span><span class="js-op">)</span> <span class="js-op">=</span> <span class="js-num">2</span> <span class="js-op">*</span> <span class="js-num">1</span> <span class="js-op">=</span> 2factorial<span class="js-op">(</span><span class="js-num">3</span><span class="js-op">)</span> <span class="js-op">=</span> <span class="js-num">3</span> <span class="js-op">*</span> <span class="js-num">2</span> <span class="js-op">=</span> 6factorial<span class="js-op">(</span><span class="js-num">4</span><span class="js-op">)</span> <span class="js-op">=</span> <span class="js-num">4</span> <span class="js-op">*</span> <span class="js-num">6</span> <span class="js-op">=</span> 24factorial<span class="js-op">(</span><span class="js-num">5</span><span class="js-op">)</span> <span class="js-op">=</span> <span class="js-num">5</span> <span class="js-op">*</span> <span class="js-num">24</span> <span class="js-op">=</span> <span class="js-num">120</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Notice that nothing gets multiplied until the base case is reached — the multiplications all happen <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">on the way back up</span>. Newcomers often expect the calculation to happen on the way <em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">down</em>; it doesn't. This one insight resolves most recursion confusion.</p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Also note the return type: <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">long</code>, because factorials explode fast (<code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">13!</code> already overflows a 32-bit int).</p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">(Suggested image: the factorial call tree — five boxes stacked going down, then arrows going back up each carrying its computed value, ending in 120. This trace visual is what students search for.)</em></p><hr class="my-6" data-streamdown="horizontal-rule" style="border-width: 1px 0px 0px; border-style: solid; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); height: 0px; margin-block: 1rem 0.75rem; --tw-space-y-reverse: 0; font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><h2 class="mt-6 mb-2 font-semibold text-2xl" data-streamdown="heading-2" dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 22.5px 0px 7.5px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-size: 1.125rem; line-height: 1.35; --tw-space-y-reverse: 0; letter-spacing: -0.105469px; --tw-font-weight: 600; margin-block: 1.25rem 0.75rem; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; background-color: rgb(18, 18, 22);">Example 2: Fibonacci — Two Recursive Calls</h2><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Fibonacci sequences appear everywhere — nature, finance, algorithm courses. Each number is the sum of the previous two: <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">0, 1, 1, 2, 3, 5, 8, 13, ...</code></p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="c" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="language-c" data-language="c" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="language-c bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;">#<span class="js-id">include</span> <span class="js-op"><</span><span class="js-id">stdio</span><span class="js-op">.</span><span class="js-id">h</span><span class="js-op">></span>
<span class="js-id">int</span> <span class="js-id">fibonacci</span><span class="js-op">(</span><span class="js-id">int</span> <span class="js-id">n</span><span class="js-op">);</span>
<span class="js-id">int</span> <span class="js-id">main</span><span class="js-op">()</span> <span class="js-op">{</span> <span class="js-id">int</span> <span class="js-id">terms</span><span class="js-op">;</span>
<span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"How many terms? "</span><span class="js-op">);</span> <span class="js-id">scanf</span><span class="js-op">(</span><span class="js-str">"%d"</span><span class="js-op">,</span> <span class="js-op">&</span><span class="js-id">terms</span><span class="js-op">);</span>
<span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"Sequence: "</span><span class="js-op">);</span> <span class="js-kw">for</span> <span class="js-op">(</span><span class="js-id">int</span> <span class="js-id">i</span> <span class="js-op">=</span> <span class="js-num">0</span><span class="js-op">;</span> <span class="js-id">i</span> <span class="js-op"><</span> <span class="js-id">terms</span><span class="js-op">;</span> <span class="js-id">i</span><span class="js-op">++)</span> <span class="js-op">{</span> <span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"%d "</span><span class="js-op">,</span> <span class="js-id">fibonacci</span><span class="js-op">(</span><span class="js-id">i</span><span class="js-op">));</span> <span class="js-op">}</span> <span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"\n"</span><span class="js-op">);</span> <span class="js-kw">return</span> <span class="js-num">0</span><span class="js-op">;}</span>
<span class="js-id">int</span> <span class="js-id">fibonacci</span><span class="js-op">(</span><span class="js-id">int</span> <span class="js-id">n</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-kw">if</span> <span class="js-op">(</span><span class="js-id">n</span> <span class="js-op"><=</span> <span class="js-num">1</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-cm">// BASE CASES: fib(0)=0, fib(1)=1 return n; }</span>
<span class="js-kw">return</span> <span class="js-id">fibonacci</span><span class="js-op">(</span><span class="js-id">n</span> <span class="js-op">-</span> <span class="js-num">1</span><span class="js-op">)</span> <span class="js-op">+</span> <span class="js-id">fibonacci</span><span class="js-op">(</span><span class="js-id">n</span> <span class="js-op">-</span> <span class="js-num">2</span><span class="js-op">);</span> <span class="js-cm">// TWO recursive calls!}</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Sample Run:</span></p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="" data-language="" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;"><span class="js-id">How</span> <span class="js-id">many</span> <span class="js-id">terms</span><span class="js-op">?</span> 10Sequence<span class="js-op">:</span> <span class="js-num">0</span> <span class="js-num">1</span> <span class="js-num">1</span> <span class="js-num">2</span> <span class="js-num">3</span> <span class="js-num">5</span> <span class="js-num">8</span> <span class="js-num">13</span> <span class="js-num">21</span> <span class="js-num">34</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">This function makes <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">two</span> recursive calls, which turns it into a branching tree of calls. That's beautiful mathematically — and a performance disaster, which brings us to a lesson this page really needs to teach.</p><hr class="my-6" data-streamdown="horizontal-rule" style="border-width: 1px 0px 0px; border-style: solid; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); height: 0px; margin-block: 1rem 0.75rem; --tw-space-y-reverse: 0; font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><h2 class="mt-6 mb-2 font-semibold text-2xl" data-streamdown="heading-2" dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 22.5px 0px 7.5px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-size: 1.125rem; line-height: 1.35; --tw-space-y-reverse: 0; letter-spacing: -0.105469px; --tw-font-weight: 600; margin-block: 1.25rem 0.75rem; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; background-color: rgb(18, 18, 22);">The Dark Side: Why Naive Fibonacci Is Slow</h2><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Compute <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">fibonacci(5)</code> and count the calls in the tree:</p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="" data-language="" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;"> <span class="js-id">fib</span><span class="js-op">(</span><span class="js-num">5</span><span class="js-op">)</span> <span class="js-op">/</span> \ <span class="js-id">fib</span><span class="js-op">(</span><span class="js-num">4</span><span class="js-op">)</span> <span class="js-id">fib</span><span class="js-op">(</span><span class="js-num">3</span><span class="js-op">)</span> <span class="js-op">/</span> \ <span class="js-op">/</span> \ <span class="js-id">fib</span><span class="js-op">(</span><span class="js-num">3</span><span class="js-op">)</span> <span class="js-id">fib</span><span class="js-op">(</span><span class="js-num">2</span><span class="js-op">)</span> <span class="js-id">fib</span><span class="js-op">(</span><span class="js-num">2</span><span class="js-op">)</span> <span class="js-id">fib</span><span class="js-op">(</span><span class="js-num">1</span><span class="js-op">)</span> <span class="js-op">/</span> \ <span class="js-op">/</span> \ <span class="js-op">/</span> \ <span class="js-id">fib</span><span class="js-op">(</span><span class="js-num">2</span><span class="js-op">)</span> <span class="js-id">fib</span><span class="js-op">(</span><span class="js-num">1</span><span class="js-op">)</span> <span class="js-op">...</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">fib(3)</code> is computed <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">twice</span>. <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">fib(2)</code> gets computed <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">three times</span>. As <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">n</code> grows, the repetition explodes exponentially — <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">fibonacci(40)</code> makes over <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">a billion</span> calls and takes many seconds, while an iterative loop computes it instantly.</p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">This is the key practical warning about recursion: <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">a correct recursive function can still be a terrible solution.</span> The fix is <em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">memoization</em> (caching results you've already computed) or simply using an iterative loop. The iterative version of Fibonacci is a two-variable loop that runs in microseconds:</p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="c" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="language-c" data-language="c" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="language-c bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;"><span class="js-id">int</span> <span class="js-id">fibIterative</span><span class="js-op">(</span><span class="js-id">int</span> <span class="js-id">n</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-kw">if</span> <span class="js-op">(</span><span class="js-id">n</span> <span class="js-op"><=</span> <span class="js-num">1</span><span class="js-op">)</span> <span class="js-kw">return</span> <span class="js-id">n</span><span class="js-op">;</span>
<span class="js-id">int</span> <span class="js-id">prev</span> <span class="js-op">=</span> <span class="js-num">0</span><span class="js-op">,</span> <span class="js-id">curr</span> <span class="js-op">=</span> <span class="js-num">1</span><span class="js-op">,</span> <span class="js-id">next</span><span class="js-op">;</span>
<span class="js-kw">for</span> <span class="js-op">(</span><span class="js-id">int</span> <span class="js-id">i</span> <span class="js-op">=</span> <span class="js-num">2</span><span class="js-op">;</span> <span class="js-id">i</span> <span class="js-op"><=</span> <span class="js-id">n</span><span class="js-op">;</span> <span class="js-id">i</span><span class="js-op">++)</span> <span class="js-op">{</span> <span class="js-id">next</span> <span class="js-op">=</span> <span class="js-id">prev</span> <span class="js-op">+</span> <span class="js-id">curr</span><span class="js-op">;</span> <span class="js-id">prev</span> <span class="js-op">=</span> <span class="js-id">curr</span><span class="js-op">;</span> <span class="js-id">curr</span> <span class="js-op">=</span> <span class="js-id">next</span><span class="js-op">;</span> <span class="js-op">}</span> <span class="js-kw">return</span> <span class="js-id">curr</span><span class="js-op">;}</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Same answer, orders of magnitude faster, constant memory. <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Recursion isn't automatically better — it's a tool with a cost.</span></p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">(Suggested image: the branching call tree with duplicate nodes highlighted in red and a "computed 3 times!" callout — this makes exponential blowup viscerally clear)</em></p><hr class="my-6" data-streamdown="horizontal-rule" style="border-width: 1px 0px 0px; border-style: solid; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); height: 0px; margin-block: 1rem 0.75rem; --tw-space-y-reverse: 0; font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><h2 class="mt-6 mb-2 font-semibold text-2xl" data-streamdown="heading-2" dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 22.5px 0px 7.5px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-size: 1.125rem; line-height: 1.35; --tw-space-y-reverse: 0; letter-spacing: -0.105469px; --tw-font-weight: 600; margin-block: 1.25rem 0.75rem; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; background-color: rgb(18, 18, 22);">Example 3: Sum of Digits — Elegant Recursion</h2><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="c" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="language-c" data-language="c" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="language-c bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;">#<span class="js-id">include</span> <span class="js-op"><</span><span class="js-id">stdio</span><span class="js-op">.</span><span class="js-id">h</span><span class="js-op">></span>
<span class="js-id">int</span> <span class="js-id">digitSum</span><span class="js-op">(</span><span class="js-id">int</span> <span class="js-id">n</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-kw">if</span> <span class="js-op">(</span><span class="js-id">n</span> <span class="js-op">==</span> <span class="js-num">0</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-cm">// base case return 0; } return (n % 10) + digitSum(n / 10); // last digit + sum of the rest}</span>
<span class="js-id">int</span> <span class="js-id">main</span><span class="js-op">()</span> <span class="js-op">{</span> <span class="js-id">int</span> <span class="js-id">num</span><span class="js-op">;</span>
<span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"Enter a number: "</span><span class="js-op">);</span> <span class="js-id">scanf</span><span class="js-op">(</span><span class="js-str">"%d"</span><span class="js-op">,</span> <span class="js-op">&</span><span class="js-id">num</span><span class="js-op">);</span>
<span class="js-kw">if</span> <span class="js-op">(</span><span class="js-id">num</span> <span class="js-op"><</span> <span class="js-num">0</span><span class="js-op">)</span> <span class="js-id">num</span> <span class="js-op">=</span> <span class="js-op">-</span><span class="js-id">num</span><span class="js-op">;</span>
<span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"Digit sum: %d\n"</span><span class="js-op">,</span> <span class="js-id">digitSum</span><span class="js-op">(</span><span class="js-id">num</span><span class="js-op">));</span> <span class="js-kw">return</span> <span class="js-num">0</span><span class="js-op">;}</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Sample Run:</span></p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="" data-language="" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;"><span class="js-id">Enter</span> <span class="js-id">a</span> <span class="js-id">number</span><span class="js-op">:</span> 4729Digit <span class="js-id">sum</span><span class="js-op">:</span> <span class="js-num">22</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">This is recursion at its most readable: <em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">"the digit sum of n is its last digit plus the digit sum of n with the last digit removed."</em> Compare that to the while-loop version from our loops cluster — same result, and the recursive form mirrors the mathematical description almost word-for-word.</p><hr class="my-6" data-streamdown="horizontal-rule" style="border-width: 1px 0px 0px; border-style: solid; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); height: 0px; margin-block: 1rem 0.75rem; --tw-space-y-reverse: 0; font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><h2 class="mt-6 mb-2 font-semibold text-2xl" data-streamdown="heading-2" dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 22.5px 0px 7.5px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-size: 1.125rem; line-height: 1.35; --tw-space-y-reverse: 0; letter-spacing: -0.105469px; --tw-font-weight: 600; margin-block: 1.25rem 0.75rem; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; background-color: rgb(18, 18, 22);">Example 4: Reversing a String</h2><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="c" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="language-c" data-language="c" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="language-c bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;">#<span class="js-id">include</span> <span class="js-op"><</span><span class="js-id">stdio</span><span class="js-op">.</span><span class="js-id">h</span><span class="js-op">></span>#<span class="js-id">include</span> <span class="js-op"><</span><span class="js-id">string</span><span class="js-op">.</span><span class="js-id">h</span><span class="js-op">></span>
<span class="js-kw">void</span> <span class="js-id">reversePrint</span><span class="js-op">(</span><span class="js-id">char</span> <span class="js-id">str</span>[]<span class="js-op">,</span> <span class="js-id">int</span> <span class="js-id">index</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-kw">if</span> <span class="js-op">(</span><span class="js-id">str</span>[<span class="js-id">index</span>] <span class="js-op">==</span> <span class="js-str">'\0'</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-cm">// base case: end of string return; }</span>
<span class="js-id">reversePrint</span><span class="js-op">(</span><span class="js-id">str</span><span class="js-op">,</span> <span class="js-id">index</span> <span class="js-op">+</span> <span class="js-num">1</span><span class="js-op">);</span> <span class="js-cm">// go to the end FIRST... putchar(str[index]); // ...then print on the way back}</span>
<span class="js-id">int</span> <span class="js-id">main</span><span class="js-op">()</span> <span class="js-op">{</span> <span class="js-id">char</span> <span class="js-id">text</span>[<span class="js-num">100</span>]<span class="js-op">;</span>
<span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"Enter text: "</span><span class="js-op">);</span> <span class="js-id">fgets</span><span class="js-op">(</span><span class="js-id">text</span><span class="js-op">,</span> <span class="js-id">sizeof</span><span class="js-op">(</span><span class="js-id">text</span><span class="js-op">),</span> <span class="js-id">stdin</span><span class="js-op">);</span> <span class="js-id">text</span>[<span class="js-id">strcspn</span><span class="js-op">(</span><span class="js-id">text</span><span class="js-op">,</span> <span class="js-str">"\n"</span><span class="js-op">)</span>] <span class="js-op">=</span> <span class="js-str">'\0'</span><span class="js-op">;</span>
<span class="js-id">reversePrint</span><span class="js-op">(</span><span class="js-id">text</span><span class="js-op">,</span> <span class="js-num">0</span><span class="js-op">);</span> <span class="js-id">putchar</span><span class="js-op">(</span><span class="js-str">'\n'</span><span class="js-op">);</span> <span class="js-kw">return</span> <span class="js-num">0</span><span class="js-op">;}</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Sample Run:</span></p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="" data-language="" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;"><span class="js-id">Enter</span> <span class="js-id">text</span><span class="js-op">:</span> <span class="js-id">recursionnoisrucer</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">The magic: <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">reversePrint</code> calls itself <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">before</span> printing. So it dives all the way to the end of the string first, then prints characters as the calls unwind — naturally producing reverse order with zero bookkeeping. This "act on the way back up" trick is a genuinely powerful recursive pattern.</p><hr class="my-6" data-streamdown="horizontal-rule" style="border-width: 1px 0px 0px; border-style: solid; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); height: 0px; margin-block: 1rem 0.75rem; --tw-space-y-reverse: 0; font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><h2 class="mt-6 mb-2 font-semibold text-2xl" data-streamdown="heading-2" dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 22.5px 0px 7.5px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-size: 1.125rem; line-height: 1.35; --tw-space-y-reverse: 0; letter-spacing: -0.105469px; --tw-font-weight: 600; margin-block: 1.25rem 0.75rem; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; background-color: rgb(18, 18, 22);">When to Use Recursion (And When Not To)</h2><div class="my-4 flex flex-col gap-2 rounded-lg bg-sidebar p-2" data-streamdown="table-wrapper" style="border: 0.8px solid rgb(47, 47, 55); margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 0.5rem; margin-block: 1rem 0.75rem; overflow: hidden; background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); gap: 0px; --tw-space-y-reverse: 0; display: flex; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px;"><div class="border-collapse" style="border: 1px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); border-collapse: collapse; border-radius: 5.5px; background-color: rgb(18, 18, 22); max-height: 300px;"><table class="w-full divide-y divide-border" data-streamdown="table" style="border-width: 0px; border-color: inherit; margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); text-indent: 0px; min-width: 100%; width: 956.8px;"><thead class="bg-muted/80" data-streamdown="table-header" style="border-width: 0px 0px 0.8px; border-color: rgb(47, 47, 55); border-image: none; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-divide-y-reverse: 0; background-color: oklab(0.252138 0.000131465 -0.00581433 / 0.8);"><tr class="" data-streamdown="table-row" style="border-color: rgb(47, 47, 55); border-image: none; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);"><th class="whitespace-nowrap px-4 py-2 text-left font-semibold text-sm" data-streamdown="table-header-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px; --tw-font-weight: 600; white-space: nowrap;">Situation</th><th class="whitespace-nowrap px-4 py-2 text-left font-semibold text-sm" data-streamdown="table-header-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px; --tw-font-weight: 600; white-space: nowrap;">Better Choice</th></tr></thead><tbody class="divide-y divide-border" data-streamdown="table-body" style="border-color: rgb(47, 47, 55); border-image: none; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);"><tr class="" data-streamdown="table-row" style="border-width: 0px 0px 0.8px; border-color: rgb(47, 47, 55); border-image: none; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-divide-y-reverse: 0;"><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;">Naturally self-similar problems (trees, nested structures, divide-and-conquer)</td><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Recursion</span></td></tr><tr class="" data-streamdown="table-row" style="border-width: 0px 0px 0.8px; border-color: rgb(47, 47, 55); border-image: none; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-divide-y-reverse: 0;"><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;">Mathematical definitions that are already recursive</td><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Recursion</span></td></tr><tr class="" data-streamdown="table-row" style="border-width: 0px 0px 0.8px; border-color: rgb(47, 47, 55); border-image: none; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-divide-y-reverse: 0;"><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;">Code clarity is the main concern and depth is small</td><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Recursion</span></td></tr><tr class="" data-streamdown="table-row" style="border-width: 0px 0px 0.8px; border-color: rgb(47, 47, 55); border-image: none; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-divide-y-reverse: 0;"><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;">Simple counts, sums, accumulation</td><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Iteration</span></td></tr><tr class="" data-streamdown="table-row" style="border-width: 0px 0px 0.8px; border-color: rgb(47, 47, 55); border-image: none; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-divide-y-reverse: 0;"><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;">Performance-critical code</td><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Iteration</span> (usually)</td></tr><tr class="" data-streamdown="table-row" style="border-width: 0px 0px 0.8px; border-color: rgb(47, 47, 55); border-image: none; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-divide-y-reverse: 0;"><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;">Very deep recursion (10,000+ levels)</td><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Iteration</span> — stack limits</td></tr><tr class="" data-streamdown="table-row" style="border-color: rgb(47, 47, 55); border-image: none; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);"><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;">Exponential naive recursion (like fib)</td><td class="px-4 py-2 text-sm" data-streamdown="table-cell" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-inline: 15px; padding-block: 7.5px; font-size: 13px; line-height: 18.75px;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Iteration or memoization</span></td></tr></tbody></table></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">A practical guideline:</span> recursion's <em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">strength</em> is expressing certain problems clearly; its <em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">cost</em> is stack memory and call overhead. When the problem structure is recursive, recursion reads beautifully and the cost is worth it. When recursion is just a fancier loop, prefer the loop.</p><hr class="my-6" data-streamdown="horizontal-rule" style="border-width: 1px 0px 0px; border-style: solid; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); height: 0px; margin-block: 1rem 0.75rem; --tw-space-y-reverse: 0; font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><h2 class="mt-6 mb-2 font-semibold text-2xl" data-streamdown="heading-2" dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 22.5px 0px 7.5px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-size: 1.125rem; line-height: 1.35; --tw-space-y-reverse: 0; letter-spacing: -0.105469px; --tw-font-weight: 600; margin-block: 1.25rem 0.75rem; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; background-color: rgb(18, 18, 22);">The Stack Overflow Trap</h2><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Since each recursive call keeps a stack frame alive, recursion depth is capped by available stack memory. Go too deep, and the program dies:</p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="c" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="language-c" data-language="c" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="language-c bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;"><span class="js-kw">void</span> <span class="js-id">infiniteRecursion</span><span class="js-op">(</span><span class="js-id">int</span> <span class="js-id">n</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"%d\n"</span><span class="js-op">,</span> <span class="js-id">n</span><span class="js-op">);</span> <span class="js-id">infiniteRecursion</span><span class="js-op">(</span><span class="js-id">n</span> <span class="js-op">+</span> <span class="js-num">1</span><span class="js-op">);</span> <span class="js-cm">// no base case!}</span>
<span class="js-cm">// Eventually: Segmentation fault (or "stack overflow")</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Segmentation fault is the classic symptom — the program crashes after printing some thousands of numbers. This is also a genuine "gotcha" when recursion depth depends on user input: <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">factorial(50000)</code> may crash not because the math is wrong, but because the stack ran out.</p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Defensive habits:</span> always define a base case first; sanity-check the input range; and if your recursion could plausibly go tens of thousands deep, think about iterating instead (or converting to an explicit stack/loop — a technique worth knowing for later).</p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">(Suggested image: stack frames piling up until the stack "runs out of room" and the program crashes — a visual of stack overflow)</em></p><hr class="my-6" data-streamdown="horizontal-rule" style="border-width: 1px 0px 0px; border-style: solid; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); height: 0px; margin-block: 1rem 0.75rem; --tw-space-y-reverse: 0; font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><h2 class="mt-6 mb-2 font-semibold text-2xl" data-streamdown="heading-2" dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 22.5px 0px 7.5px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-size: 1.125rem; line-height: 1.35; --tw-space-y-reverse: 0; letter-spacing: -0.105469px; --tw-font-weight: 600; margin-block: 1.25rem 0.75rem; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; background-color: rgb(18, 18, 22);">The Classic Recursion Mistakes</h2><ol class="list-inside list-decimal whitespace-normal [li_&]:pl-6" data-streamdown="ordered-list" style="border: 0px solid rgb(47, 47, 55); margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); list-style: outside decimal; padding-inline-start: 1.375rem; margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><li class="py-1 [&>p]:inline" data-streamdown="list-item" dir="ltr" style="border: 0px solid rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-block: 0.125rem;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">No base case</span> — infinite recursion → stack overflow crash.</li><li class="py-1 [&>p]:inline" data-streamdown="list-item" dir="ltr" style="border: 0px solid rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-block: 0.125rem;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Base case that's never reached</span> — e.g., <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">if (n == 0)</code> when the recursive call is <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">rec(n - 2)</code>, so n skips right past 0 and goes negative forever. The shrinking step must actually land on the base case.</li><li class="py-1 [&>p]:inline" data-streamdown="list-item" dir="ltr" style="border: 0px solid rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-block: 0.125rem;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Base case present but broken</span> — returning the wrong value (e.g., <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">return 0;</code> for factorial's base case gives you 0 every time).</li><li class="py-1 [&>p]:inline" data-streamdown="list-item" dir="ltr" style="border: 0px solid rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-block: 0.125rem;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Not shrinking the problem</span> — calling <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">rec(n)</code> with the <em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">same</em> <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">n</code> from inside <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">rec(n)</code> — guaranteed infinite recursion.</li><li class="py-1 [&>p]:inline" data-streamdown="list-item" dir="ltr" style="border: 0px solid rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-block: 0.125rem;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Expecting work to happen on the way down</span> — in most accumulator-style recursions, the combination happens on the way <em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">back up</em>. If you're confused about output order, trace the unwinding.</li><li class="py-1 [&>p]:inline" data-streamdown="list-item" dir="ltr" style="border: 0px solid rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-block: 0.125rem;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Ignoring the cost</span> — naive Fibonacci is the cautionary tale. Correct code, unusable performance.</li><li class="py-1 [&>p]:inline" data-streamdown="list-item" dir="ltr" style="border: 0px solid rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); padding-block: 0.125rem;"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Confusing recursion with iteration mentally</span> — mixing up "this happens per call" vs "this happens per unwind." Write the trace out by hand once or twice; it becomes obvious.</li></ol><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">(Suggested image: "7 Recursion Mistakes" checklist graphic — consistent with the series)</em></p><hr class="my-6" data-streamdown="horizontal-rule" style="border-width: 1px 0px 0px; border-style: solid; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); height: 0px; margin-block: 1rem 0.75rem; --tw-space-y-reverse: 0; font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><h2 class="mt-6 mb-2 font-semibold text-2xl" data-streamdown="heading-2" dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 22.5px 0px 7.5px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-size: 1.125rem; line-height: 1.35; --tw-space-y-reverse: 0; letter-spacing: -0.105469px; --tw-font-weight: 600; margin-block: 1.25rem 0.75rem; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; background-color: rgb(18, 18, 22);">A Complete Example: Tower of Hanoi</h2><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">The legendary puzzle, and the moment recursion feels like genuine magic. Move <code class="rounded bg-muted px-1.5 py-0.5 font-mono text-sm" data-streamdown="inline-code" dir="ltr" style="border-width: 0px; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 0.8125rem; user-select: text; border-radius: 0.25rem; background-color: rgb(33, 34, 37); padding-inline: 5.625px; padding-block: 1.875px; line-height: 18.75px; padding: 0.1em 0.35em;">n</code> disks from peg A to peg C, one at a time, never placing a larger disk on a smaller one:</p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="c" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="language-c" data-language="c" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="language-c bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;">#<span class="js-id">include</span> <span class="js-op"><</span><span class="js-id">stdio</span><span class="js-op">.</span><span class="js-id">h</span><span class="js-op">></span>
<span class="js-id">int</span> <span class="js-id">moves</span> <span class="js-op">=</span> <span class="js-num">0</span><span class="js-op">;</span>
<span class="js-kw">void</span> <span class="js-id">hanoi</span><span class="js-op">(</span><span class="js-id">int</span> <span class="js-id">n</span><span class="js-op">,</span> <span class="js-id">char</span> <span class="js-kw">from</span><span class="js-op">,</span> <span class="js-id">char</span> <span class="js-id">to</span><span class="js-op">,</span> <span class="js-id">char</span> <span class="js-id">via</span><span class="js-op">)</span> <span class="js-op">{</span>
<span class="js-kw">if</span> <span class="js-op">(</span><span class="js-id">n</span> <span class="js-op">==</span> <span class="js-num">1</span><span class="js-op">)</span> <span class="js-op">{</span> <span class="js-cm">// BASE CASE: one disk</span>
<span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"Move disk 1 from %c to %c\n"</span><span class="js-op">,</span> <span class="js-kw">from</span><span class="js-op">,</span> <span class="js-id">to</span><span class="js-op">);</span>
<span class="js-id">moves</span><span class="js-op">++;</span>
<span class="js-kw">return</span><span class="js-op">;</span>
<span class="js-op">}</span>
<span class="js-id">hanoi</span><span class="js-op">(</span><span class="js-id">n</span> <span class="js-op">-</span> <span class="js-num">1</span><span class="js-op">,</span> <span class="js-kw">from</span><span class="js-op">,</span> <span class="js-id">via</span><span class="js-op">,</span> <span class="js-id">to</span><span class="js-op">);</span> <span class="js-cm">// step 1: move n-1 to the spare peg</span>
<span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"Move disk %d from %c to %c\n"</span><span class="js-op">,</span> <span class="js-id">n</span><span class="js-op">,</span> <span class="js-kw">from</span><span class="js-op">,</span> <span class="js-id">to</span><span class="js-op">);</span>
<span class="js-id">moves</span><span class="js-op">++;</span>
<span class="js-id">hanoi</span><span class="js-op">(</span><span class="js-id">n</span> <span class="js-op">-</span> <span class="js-num">1</span><span class="js-op">,</span> <span class="js-id">via</span><span class="js-op">,</span> <span class="js-id">to</span><span class="js-op">,</span> <span class="js-kw">from</span><span class="js-op">);</span> <span class="js-cm">// step 2: move n-1 onto the target</span>
<span class="js-op">}</span>
<span class="js-id">int</span> <span class="js-id">main</span><span class="js-op">()</span> <span class="js-op">{</span>
<span class="js-id">int</span> <span class="js-id">disks</span><span class="js-op">;</span>
<span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"Number of disks: "</span><span class="js-op">);</span>
<span class="js-id">scanf</span><span class="js-op">(</span><span class="js-str">"%d"</span><span class="js-op">,</span> <span class="js-op">&</span><span class="js-id">disks</span><span class="js-op">);</span>
<span class="js-id">hanoi</span><span class="js-op">(</span><span class="js-id">disks</span><span class="js-op">,</span> <span class="js-str">'A'</span><span class="js-op">,</span> <span class="js-str">'C'</span><span class="js-op">,</span> <span class="js-str">'B'</span><span class="js-op">);</span>
<span class="js-id">printf</span><span class="js-op">(</span><span class="js-str">"Total moves: %d\n"</span><span class="js-op">,</span> <span class="js-id">moves</span><span class="js-op">);</span>
<span class="js-kw">return</span> <span class="js-num">0</span><span class="js-op">;</span>
<span class="js-op">}</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Sample Run (3 disks):</span></p><div class="my-4 flex w-full flex-col gap-2 rounded-xl bg-sidebar p-2" data-language="" data-streamdown="code-block" dir="ltr" style="border-width: medium; border-style: none; border-color: currentcolor; border-image: none; margin: 0px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); max-width: 100%; border-radius: 7.5px; margin-block: 1rem 0.75rem; background: 0px 0px rgb(18, 18, 22); gap: 0px; --tw-space-y-reverse: 0; display: flex; width: 960px; flex-direction: column; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; content-visibility: auto; contain-intrinsic-size: auto 200px;"><div class="" data-language="" data-streamdown="code-block-body" dir="ltr" style="border: 1px solid rgb(47, 47, 55); padding: 0.625rem 0.75rem; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); background: none 0% 0% / auto repeat scroll padding-box border-box rgb(24, 25, 27); border-radius: 0.5rem; font-size: 0.8125rem; line-height: 1.6; max-height: 400px;"><div class="code-card position-relative my-2">
<div class="code-card-actions">
<button type="button" class="btn-code-action copy-code-btn" onclick="copyCode(this)" title="Copy Code">
<i class="far fa-copy"></i>
</button>
<a href="/tools/c-compiler" target="_blank" class="btn-code-action run-code-btn" title="Run Online">
<i class="fas fa-play"></i>
</a>
</div>
<pre class="bg-[var(--sdm-bg,inherit)] dark:bg-[var(--shiki-dark-bg,var(--sdm-bg,inherit))] code-box" style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text; background: 0px 0px; --sdm-bg: transparent; --sdm-fg: inherit;"><code style="border-width: 0px; border-style: solid; border-color: rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-family: "Geist Mono Variable", ui-monospace, SFMono-Regular, Menlo, Consolas, "Liberation Mono", monospace; font-feature-settings: normal; font-variation-settings: normal; font-size: 1em; user-select: text;"><span class="js-id">Number</span> <span class="js-kw">of</span> <span class="js-id">disks</span><span class="js-op">:</span> <span class="js-num">3</span>
<span class="js-id">Move</span> <span class="js-id">disk</span> <span class="js-num">1</span> <span class="js-kw">from</span> <span class="js-id">A</span> <span class="js-id">to</span> <span class="js-id">C</span>
<span class="js-id">Move</span> <span class="js-id">disk</span> <span class="js-num">2</span> <span class="js-kw">from</span> <span class="js-id">A</span> <span class="js-id">to</span> <span class="js-id">B</span>
<span class="js-id">Move</span> <span class="js-id">disk</span> <span class="js-num">1</span> <span class="js-kw">from</span> <span class="js-id">C</span> <span class="js-id">to</span> <span class="js-id">B</span>
<span class="js-id">Move</span> <span class="js-id">disk</span> <span class="js-num">3</span> <span class="js-kw">from</span> <span class="js-id">A</span> <span class="js-id">to</span> <span class="js-id">C</span>
<span class="js-id">Move</span> <span class="js-id">disk</span> <span class="js-num">1</span> <span class="js-kw">from</span> <span class="js-id">B</span> <span class="js-id">to</span> <span class="js-id">A</span>
<span class="js-id">Move</span> <span class="js-id">disk</span> <span class="js-num">2</span> <span class="js-kw">from</span> <span class="js-id">B</span> <span class="js-id">to</span> <span class="js-id">C</span>
<span class="js-id">Move</span> <span class="js-id">disk</span> <span class="js-num">1</span> <span class="js-kw">from</span> <span class="js-id">A</span> <span class="js-id">to</span> <span class="js-id">C</span>
<span class="js-id">Total</span> <span class="js-id">moves</span><span class="js-op">:</span> <span class="js-num">7</span></code></pre></div></div></div><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Now find the loop-based version of this. There isn't a natural, readable one — this is recursion's home turf: an inherently self-similar structure expressed in nine lines. Note the base case count too: 3 disks → 7 moves (2³ − 1). Tower of Hanoi is the final destination of every recursion tutorial, and now it's your destination too.</p><hr class="my-6" data-streamdown="horizontal-rule" style="border-width: 1px 0px 0px; border-style: solid; border-color: rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); height: 0px; margin-block: 1rem 0.75rem; --tw-space-y-reverse: 0; font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);"><h2 class="mt-6 mb-2 font-semibold text-2xl" data-streamdown="heading-2" dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 22.5px 0px 7.5px; padding: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); font-size: 1.125rem; line-height: 1.35; --tw-space-y-reverse: 0; letter-spacing: -0.105469px; --tw-font-weight: 600; margin-block: 1.25rem 0.75rem; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; background-color: rgb(18, 18, 22);">Final Thoughts</h2><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Recursion is a shift in how you think, not just what you type: instead of <em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">"first do X, then do Y, then Z,"</em> you learn to say <em style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5);">"assume the smaller version is already solved — now build on that."</em> Once that reframe clicks, problems you'd have written twenty lines of loop code for collapse into three elegant lines.</p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Keep the two-rule discipline — <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">base case, and shrink toward it</span> — and the call-stack picture in mind. And stay honest about cost: recursion buys clarity, and sometimes it charges performance and stack depth. Knowing which one you're paying is what separates a clever solution from a good one.</p><p dir="ltr" style="border: 0px solid rgb(47, 47, 55); margin: 0px; outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); margin-block: 0px 0.75rem; --tw-space-y-reverse: 0; color: rgb(252, 252, 253); font-family: "Inter Variable", sans-serif; font-size: 13px; background-color: rgb(18, 18, 22);">Next in this cluster: <span class="font-semibold" data-streamdown="strong" style="border: 0px solid rgb(47, 47, 55); outline-color: oklab(0.51773 0.045283 -0.122431 / 0.5); --tw-font-weight: 600; font-weight: 600;">Scope and Lifetime of Variables</span> — which explains, among other things, why each recursive call gets its own local variables, as you've just seen.</p>
Code Example
#include <stdio.h>
// Recursive factorial function
unsigned long long factorial(unsigned int n) {
// Base case
if (n <= 1) {
return 1;
}
// Recursive step
return n * factorial(n - 1);
}
int main() {
unsigned int num = 6;
printf("Factorial of %u is: %llu\
", num, factorial(num));
return 0;
}Interview Question & Tips
A: If the recursion depth is too large or the base case is missing, excessive stack frames consume all available thread stack memory (typically 1-8 MB), causing a crash.
Q: When should iteration be preferred over recursion in C?
A: In performance-critical and memory-constrained embedded systems, because iteration uses a constant stack footprint $O(1)$ compared to $O(N)$ stack memory.
Best Practices
This study reference for Recursion in C: Self-Calling Functions and Recursive Problem Solving is curated and verified against recognized curriculum benchmarks, peer-reviewed textbooks, and official technical documentation: