Recursion

Review of Iteration

Last week, we learned two methods for iterating, or looping, over blocks of code. Let’s look at an example from our lab on Friday. The function sum_n(n)defines a function that sums the values from 1 to n. Given the number 10, it would compute the sum to be 1 + 2 + 3 + … + 10. This gives us a total of 55. Since we know exactly how many times the loop is going to run, a for-loop is probably our first option. However, we can also solve this problem using a while loop. We can either count up to nor down from to 0, stopping when we reach one of our endpoints. Below the following code is shown using both a for-loop and while-loop.

Keep this example in mind. We will come back to it!

Let’s look at another example. Pretend we have a wash machine that can only get the clothes 75% clean. We will quantify how dirty clothes are numerically, and when the wash completes, the dirt level will be reduced by 75%. How will we know if our clothes are clean? Let’s set a threshold. If our clothes have a dirt level of 10 or less, we will call them clean. Otherwise, they are still dirty.

What happens if they are still dirty after washing? We can call another function that will “rewash” our clothes. The same criteria applies. If the clothes have a dirt level of less than 10, we will say that they are clean. Otherwise, we will call a third function that re-rewashes our clothes. Take a look at the code below.

What do you notice about these functions? A couple of things stick out. 1. If the clothes need to be washed more than 3 times, they just come back dirty by our standard. *holds nose* Secondly, washClothesrewashClothes, and rerewashClotheslook quite similar! Could we just recall washClothesinstead? Of course! That is the basic idea of recursion!

Walk through the example below. Notice that our clothes always come back clean! You can try different dirt levels and see for yourself.

Take a look at this next example. Do you remember when you were 4 years old and your favorite question was ‘Why?’ In this example, we look at running the same task over and over again until the user decides to end the function. You may look at this problem and conclude that it may also be solved using iteration. That is also correct; however, let’s think about this problem recursively.

Small Subtasks

One main reason for writing recursive solutions is that it allows the program to solve a problem by diving it into simple and smaller tasks.  By solving each of these simpler tasks, when can then compute much larger tasks. We will look at two mathematical examples, computing factorials and squares of a number. The factorial of n can be computed by the product of 1, 2, …, n. Therefore, the factorial(5)is 1 * 2 * 3 * 4 * 5. We could also write the factorial of 5 as the factorial(4) * 5, since the factorial(4) is 1 * 2 * 3 * 4. By this same logic, the factorial(4) could be written as the factorial(3) * 4. Let’s take a moment to write this out in detail

factorial(5) = 1 * 2 * 3 * 4 * 5

which also equals factorial(4) * 5

which also equals factorial(3) * 4 * 5

which also equals factorial(2) * 3 * 4 * 5

which equals the factorials(1) * 2 * 3 * 4 * 5

Generally speaking, thefactorial(n) isfactorial(n-1) * n.

Now, that we have generated a recursive solution, we just need a base case. This tells us when to stop. We don’t want to compute the factorials of negative numbers because those don’t exist! If n equals 0, let’s return 1, since that is the definition of the factorial of 0.

We can translate this pseudocode into code.

Did you know that you can easily compute the next square if you know the the previous square. For example, let’s compute the square of 21. You could multiple 21 * 21 computationally, or you could use your knowledge of 20 * 20 to quickly compute 21 * 21. The square of 21 equals the (square of 20) + 20 + 21. 
Generally speaking, (n+1)^2  = n^2 + n + (n+1). Notice that the square of n+1 is defined in terms of n^2. This is a recursive problem! We can use the same function to solve a smaller problem. Once we have the solution to our smaller problem, we can go back and solve our larger problem. Take a look at the code below.

Now, using the examples that we have shown, try to write a solution to the sum_n function using a recursive solution! A blank template is available for you. Fill it in and press run! Try not to peak at the solution.

No peaking!

Ok, here’s an answer. Your solution may be slightly different and that is ok!

Solution:

css.php