Lecture 8: April 25, 2024

Reading: zyBooks text, §10.1–10.2, 10.5, 10.8
Assignments: Homework 2, due May 6

1. Recursion
   1. Expressing a problem in terms of a simpler version of itself — use n!
   2. Function calling itself
   3. Similar to mathematical induction, but backwards
   4. Structure: base case, recursive case
   5. What happens if you omit the base case? (Bad things …)

2. How it works
   1. Program stack
   2. Walk through nfact.c, with n = 4
   3. Note nfact calls nfact

3. Recursive greatest common divisor
   1. Go through Euclidean algorithm for computing gcd
   2. Walk through function gcd, with m = 4 and n = 6
   3. Do it again with m = 126 and n = 28
   4. Go through program gcd.c

4. Recursive palindrome program
   1. Go through algorithm, working from outside in
   2. Write recursive case
   3. Write base case
   4. Put them together in ispal.c

5. Tower of Hanoi [tower.c]

Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: mabishop@ucdavis.edu

ECS 36A, Programming & Problem Solving Version of April 24, 2024 at 6:28AM

You can also obtain a PDF version of this.