**CS 1109: Fundamental Programming Concepts (Summer 2023)** [Home](../index.md.html) • [Schedule](../schedule.md.html) • [Syllabus](../syllabus.md.html) • [Assignments](../assignments.md.html) • [Labs](../labs.md.html) (#) Lab 10: Recursion In this lab you will practice writing simple recursive functions. !!! note: Due Date This lab is due **Monday, July 31st, 2023 at 4:00pm EDT**. (#) Recursion Review Yesterday in class you were introduced to the idea that functions can call themselves in order do something repeatedly. These types of functions are called **recursive functions**. The process of *executing* a recursive function is called **recursion**. While many simple problems could more easily be solved with iteration, recursion enables other problems to be solved simply, concisely, and elegantly. The first step to writing any recursive function is to first *decompose* the problem into two parts: the **base case** and the **recursive case**. The **base case** is the condition when the recursion *stops*. Often the base case is the "simplest" or "smallest" solution to a problem. If you forget to include a base case in your recursive functions, the function will likely infinitely recurse until it crashes. On the other hand, the **recursive case** is where most of the "work" happens in the function where the function calls itself on a *smaller* input. For example, consider the function `factorial(n)` which returns $n! = n \times (n-1) \times \cdots \times 1$ where $n$ is a positive integer. We first have to figure out the base case and the recursive case for the factorial function. - **Base Case:** It is often handy to consider what a recursive function should do when it is provided with the "smallest" valid input. In this case, since `factorial` is only defined for positive integers, the smallest valid input would be `n = 1`, or computing $1!$. However, $1! = 1$! So, `factorial(1)` should return 1. - **Recursive Case:** Now, we need to figure out what `factorial(n)` whould do when `n` is greater than 1. Notice how we can rewrite $n! = n \times (n-1) \times \cdots \times 1$ into $n! = n * (n-1)!$. So, we can compute $n!$ by first computing $(n-1)!$ and then multiplying $(n-1)!$ by $n$!. Well, since we are writing the `factorial` function, we can recursively call our `factorial` function to give us $(n-1)!$. Now we can proceed with writing `factorial(n)`. ~~~ python listing def factorial(n): """ Returns n! where n! = n * n-1 * n-2 * ... * 1. Precondition: n is a positive int """ # Base Case: n == 1 if n == 1: return 1 else: # Recursive Case: n * factorial return n * factorial(n - 1) ~~~ If `n` is 1, `factorial` simply returns 1. Otherwise, it multiplies `n` by the result of calling `factorial(n - 1)`, which would compute $(n-1)!$. What happens when `factorial(4)` is called? - The execution of `factorial(4)` begins with `n = 4`, and since `n` is not equal to 1, execution enters the recursive case where the function calls itself on `n - 1` or `3`. - The execution of `factorial(3)` begins with `n = 3`, and since `n` is not equal to 1, execution enters the recursive case where the function calls itself on `n - 1` or `2` - The execution of `factorial(2)` begins with `n = 2`, and since `n` is not equal to 1, execution enters the recursive case where the function calls itself on `n - 1` or `1` - The execution of `factorial(1)` begins with `n = 1`, but now since `n` is equal to 1, execution enters the base case where 1 is returned back to the caller. - The execution of `factorial(2)` receives the return value 1 from calling `factorial(1)`, multiplies it by `n`, which is 2, and returns the product, or $2 \times 1 = 2$, to the caller. - The execution of `factorial(3)` receives the return value 2 from calling `factorial(2)`, multiplies it by `n`, which is 3, and returns the product, or $3 \times 2 = 6$, to the caller. - The execution of `factorial(4)` receives the return value 6 from calling `factorial(3)`, multiplies it by `n`, which is 4, and returns the product, or $4 \times 6 = 24$. Now that `factorial(4)` has returned 24, the function call has finished executing. (#) Instructions 1. Download the starter code for this lab: Click here to download `lab10.py`. 2. Open `lab10.py` in VSCode and save it in your `cs1109` folder that we have been using in the course. 3. Implement each of the functions in `lab10.py`. 4. Be sure to *test* each of your functions. You do not need to write test cases, but you should absolutely call your functions on a number of inputs to convince yourself that you have implemented them correctly. (#) Submission Upload `lab10.py` to Gradescope when you are finished. ------------------------------------------------------------------------------- Copyright © [Zachary J. Susag](https://zacharysusag.net)  Unless specified elsewhere on this page, this work is licensed under a [Creative Commons Attribution-ShareAlike 4.0 International License](http://creativecommons.org/licenses/by-sa/4.0/). -------------------------------------------------------------------------------