| 1 | <!DOCTYPE html> |
| 2 | <html lang="en"> |
| 3 | <head> |
| 4 | <meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1"> |
| 5 | <title>Module 04 · Recursion · CS101</title> |
| 6 | <link rel="stylesheet" href="../../../assets/fonts.css"> |
| 7 | <link rel="stylesheet" href="../../../assets/base.css"> |
| 8 | <link rel="stylesheet" href="../../../assets/animations/animations.css"> |
| 9 | <link rel="stylesheet" href="style.css"> |
| 10 | </head> |
| 11 | <body class="tpl-course-module"> |
| 12 | <div class="deck"> |
| 13 | |
| 14 | <!-- 1. Cover --> |
| 15 | <section class="slide full" data-title="Cover"> |
| 16 | <p class="kicker">CS 101 · MODULE 04</p> |
| 17 | <h1 class="h1 mt-s">Recursion: solving<br>problems by <em>calling yourself</em>.</h1> |
| 18 | <p class="lede mt-l" style="max-width:62ch">In this module you'll learn why a function that calls itself is not a trick, but the most natural way to describe problems that contain smaller copies of themselves.</p> |
| 19 | <div class="row mt-l" style="gap:16px"> |
| 20 | <span class="pill-academic">~ 45 min read</span> |
| 21 | <span class="pill-academic">prereq · functions, if/else</span> |
| 22 | <span class="pill-academic">lang · Python</span> |
| 23 | </div> |
| 24 | <div class="deck-footer"><span>Dr. A. Rivera · Spring 2026</span><span class="slide-number" data-current="1" data-total="7"></span></div> |
| 25 | </section> |
| 26 | |
| 27 | <!-- 2. Objectives --> |
| 28 | <section class="slide" data-title="Objectives"> |
| 29 | <aside class="sidebar"> |
| 30 | <div class="brand">CS 101 · M04</div> |
| 31 | <h5>Learning objectives</h5> |
| 32 | <ul class="obj-list"> |
| 33 | <li class="current">Define recursion</li> |
| 34 | <li>Identify a base case</li> |
| 35 | <li>Trace a recursive call</li> |
| 36 | <li>Convert loop ↔ recursion</li> |
| 37 | <li>Recognize when recursion helps</li> |
| 38 | </ul> |
| 39 | <h5>Module progress</h5> |
| 40 | <p class="dim" style="font-size:13px">Page 2 of 7 · ~5 min in</p> |
| 41 | </aside> |
| 42 | <div class="main"> |
| 43 | <p class="kicker">OBJECTIVES</p> |
| 44 | <h2 class="h2 mt-s">By the end, you will be able to…</h2> |
| 45 | <div class="stack mt-l"> |
| 46 | <div class="concept-box"><h4>① Explain recursion in one sentence.</h4><p class="dim">"A function that solves a problem by calling itself on a smaller version of that problem."</p></div> |
| 47 | <div class="concept-box"><h4>② Write a base case that always terminates.</h4><p class="dim">Every recursive function must have an exit door, or it runs forever.</p></div> |
| 48 | <div class="concept-box"><h4>③ Trace a call stack on paper.</h4><p class="dim">Given <code>fact(4)</code>, draw the stack frames top-to-bottom.</p></div> |
| 49 | <div class="concept-box"><h4>④ Convert a while-loop to a recursive equivalent.</h4><p class="dim">And explain when one is clearer than the other.</p></div> |
| 50 | </div> |
| 51 | </div> |
| 52 | </section> |
| 53 | |
| 54 | <!-- 3. Concept --> |
| 55 | <section class="slide" data-title="Concept"> |
| 56 | <aside class="sidebar"> |
| 57 | <div class="brand">CS 101 · M04</div> |
| 58 | <h5>Learning objectives</h5> |
| 59 | <ul class="obj-list"> |
| 60 | <li class="done">Define recursion</li> |
| 61 | <li class="current">Identify a base case</li> |
| 62 | <li>Trace a recursive call</li> |
| 63 | <li>Convert loop ↔ recursion</li> |
| 64 | <li>Recognize when recursion helps</li> |
| 65 | </ul> |
| 66 | <h5>Key terms</h5> |
| 67 | <p class="dim" style="font-size:13px">base case · recursive case · call stack · tail call</p> |
| 68 | </aside> |
| 69 | <div class="main"> |
| 70 | <p class="kicker">CORE CONCEPT</p> |
| 71 | <h2 class="h2 mt-s">Two parts, always.</h2> |
| 72 | <p class="lede mt-m">A recursive function has exactly two things inside it: a <b>base case</b> (when to stop) and a <b>recursive case</b> (how to shrink the problem before calling yourself).</p> |
| 73 | <div class="callout"> |
| 74 | <b>Rule of thumb.</b> If you can't name the base case out loud, don't write the recursion yet. Draw it on paper first. |
| 75 | </div> |
| 76 | <div class="grid g2 mt-l"> |
| 77 | <div class="concept-box"><h4>Base case</h4><p class="dim">The smallest possible input — one the function answers directly, without calling itself.</p><p class="pill-academic">e.g. <b>n == 0</b></p></div> |
| 78 | <div class="concept-box"><h4>Recursive case</h4><p class="dim">Every other input — delegate to a smaller version of the same problem.</p><p class="pill-academic">e.g. <b>n × fact(n-1)</b></p></div> |
| 79 | </div> |
| 80 | </div> |
| 81 | </section> |
| 82 | |
| 83 | <!-- 4. Example --> |
| 84 | <section class="slide" data-title="Example"> |
| 85 | <aside class="sidebar"> |
| 86 | <div class="brand">CS 101 · M04</div> |
| 87 | <h5>Learning objectives</h5> |
| 88 | <ul class="obj-list"> |
| 89 | <li class="done">Define recursion</li> |
| 90 | <li class="done">Identify a base case</li> |
| 91 | <li class="current">Trace a recursive call</li> |
| 92 | <li>Convert loop ↔ recursion</li> |
| 93 | <li>Recognize when recursion helps</li> |
| 94 | </ul> |
| 95 | <h5>Try it yourself</h5> |
| 96 | <p class="dim" style="font-size:13px">Open repl.it and run the code on the right. Then try <code>fact(10)</code>.</p> |
| 97 | </aside> |
| 98 | <div class="main"> |
| 99 | <p class="kicker">WORKED EXAMPLE</p> |
| 100 | <h2 class="h2 mt-s">Factorial, 7 lines.</h2> |
| 101 | <div class="code mt-m"><pre style="margin:0"><span class="cmt"># fact(n) = n × (n-1) × … × 1, and fact(0) = 1</span> |
| 102 | <span class="kw">def</span> fact(n): |
| 103 | <span class="kw">if</span> n == <span class="str">0</span>: <span class="cmt"># base case</span> |
| 104 | <span class="kw">return</span> <span class="str">1</span> |
| 105 | <span class="kw">return</span> n * fact(n - <span class="str">1</span>) <span class="cmt"># recursive case</span> |
| 106 | |
| 107 | <span class="kw">print</span>(fact(<span class="str">4</span>)) <span class="cmt"># → 24</span></pre></div> |
| 108 | <div class="callout"> |
| 109 | <b>Trace fact(4).</b> 4 × fact(3) → 4 × (3 × fact(2)) → 4 × 3 × (2 × fact(1)) → 4 × 3 × 2 × 1 × fact(0) → 4 × 3 × 2 × 1 × 1 = <b>24</b>. |
| 110 | </div> |
| 111 | </div> |
| 112 | </section> |
| 113 | |
| 114 | <!-- 5. Exercise --> |
| 115 | <section class="slide" data-title="Exercise"> |
| 116 | <aside class="sidebar"> |
| 117 | <div class="brand">CS 101 · M04</div> |
| 118 | <h5>Learning objectives</h5> |
| 119 | <ul class="obj-list"> |
| 120 | <li class="done">Define recursion</li> |
| 121 | <li class="done">Identify a base case</li> |
| 122 | <li class="done">Trace a recursive call</li> |
| 123 | <li class="current">Convert loop ↔ recursion</li> |
| 124 | <li>Recognize when recursion helps</li> |
| 125 | </ul> |
| 126 | <h5>Time</h5> |
| 127 | <p class="dim" style="font-size:13px">~10 minutes · solo</p> |
| 128 | </aside> |
| 129 | <div class="main"> |
| 130 | <p class="kicker">EXERCISE 4.1</p> |
| 131 | <h2 class="h2 mt-s">Write <em>sum_to(n)</em>.</h2> |
| 132 | <p class="lede mt-m">Return <code>1 + 2 + … + n</code> using recursion — no loops allowed.</p> |
| 133 | <div class="exercise mt-l"> |
| 134 | <p style="margin:0;font-size:18px;color:var(--text-1)"><b>Your task</b></p> |
| 135 | <ol style="color:var(--text-2);line-height:1.8;margin:10px 0 0"> |
| 136 | <li>Write the base case. What does <code>sum_to(0)</code> return?</li> |
| 137 | <li>Write the recursive case in terms of <code>sum_to(n - 1)</code>.</li> |
| 138 | <li>Test it: <code>sum_to(5) == 15</code>, <code>sum_to(10) == 55</code>.</li> |
| 139 | <li>Bonus: what happens if you call <code>sum_to(-3)</code>? Fix it.</li> |
| 140 | </ol> |
| 141 | </div> |
| 142 | <p class="dim mt-m" style="font-size:14px">Stuck? Remember: a base case is the smallest input you already know the answer to.</p> |
| 143 | </div> |
| 144 | </section> |
| 145 | |
| 146 | <!-- 6. Check understanding --> |
| 147 | <section class="slide" data-title="Check"> |
| 148 | <aside class="sidebar"> |
| 149 | <div class="brand">CS 101 · M04</div> |
| 150 | <h5>Learning objectives</h5> |
| 151 | <ul class="obj-list"> |
| 152 | <li class="done">Define recursion</li> |
| 153 | <li class="done">Identify a base case</li> |
| 154 | <li class="done">Trace a recursive call</li> |
| 155 | <li class="done">Convert loop ↔ recursion</li> |
| 156 | <li class="current">Recognize when recursion helps</li> |
| 157 | </ul> |
| 158 | <h5>Self-assess</h5> |
| 159 | <p class="dim" style="font-size:13px">You should get 3/3.</p> |
| 160 | </aside> |
| 161 | <div class="main"> |
| 162 | <p class="kicker">CHECK YOUR UNDERSTANDING</p> |
| 163 | <h2 class="h2 mt-s">Which function will recurse forever?</h2> |
| 164 | <div class="mt-l"> |
| 165 | <div class="mcq"><div class="letter">A</div><div><b>def f(n): return 1 if n == 0 else n * f(n - 1)</b><p class="dim" style="font-size:13px;margin:4px 0 0">Base case <code>n == 0</code>, shrinks toward it. Terminates.</p></div></div> |
| 166 | <div class="mcq correct"><div class="letter">B</div><div><b>def f(n): return n + f(n + 1)</b><p class="dim" style="font-size:13px;margin:4px 0 0"><b style="color:var(--accent)">✓ Correct.</b> No base case, and <code>n</code> grows — infinite recursion.</p></div></div> |
| 167 | <div class="mcq"><div class="letter">C</div><div><b>def f(n): return n if n < 2 else f(n - 1) + f(n - 2)</b><p class="dim" style="font-size:13px;margin:4px 0 0">Classic Fibonacci. Base case on <code>n < 2</code>. Terminates.</p></div></div> |
| 168 | </div> |
| 169 | </div> |
| 170 | </section> |
| 171 | |
| 172 | <!-- 7. Summary --> |
| 173 | <section class="slide full" data-title="Summary"> |
| 174 | <p class="kicker">SUMMARY · MODULE 04</p> |
| 175 | <h1 class="h1 mt-s">You can now…</h1> |
| 176 | <div class="grid g2 mt-l"> |
| 177 | <div class="concept-box"><h4>✓ Define recursion</h4><p class="dim">A function that calls itself on a smaller input.</p></div> |
| 178 | <div class="concept-box"><h4>✓ Write a safe base case</h4><p class="dim">Every recursion needs an exit door.</p></div> |
| 179 | <div class="concept-box"><h4>✓ Trace a call stack</h4><p class="dim">You can unwind <code>fact(4)</code> by hand.</p></div> |
| 180 | <div class="concept-box"><h4>✓ Judge when to use it</h4><p class="dim">Trees and self-similar problems → recursion. Flat iteration → loop.</p></div> |
| 181 | </div> |
| 182 | <div class="callout mt-l"> |
| 183 | <b>Up next · Module 05.</b> Divide & conquer: merge sort. We'll use everything you just learned — but on lists, not numbers. |
| 184 | </div> |
| 185 | </section> |
| 186 | |
| 187 | </div> |
| 188 | <script src="../../../assets/runtime.js"></script> |
| 189 | </body></html> |
| 190 |