Land Without Loops

LAB8

Welcome

While flying your small plane along the northeastern coast of the United States, you get lost in a storm and have to make an emergency landing on an uncharted island with many ivory towers. You end up befriending the residents who tell you their island is named Haskellia and they subsist on curry dishes made from local spices and herbs. They are very fond of programming—an essential part of worship at their Church of Alonzo—but have not heard of Python. In fact, they are shocked and dismayed when you show them for-loops and while-loops. Still, they welcome you and begin to teach you their ways.

What We Will Learn

What recursion is The simplest kind of recursion Conditional expressions Integer division

Activity

While on the island, you offer to help out some little ones make their favorite skinny block pyramids. They look like this:

You’re asked by their teacher to write some code to determine how many blocks are needed to make a pyramid of height $n$. In your head, you know you just need to write:

def blocks_needed(n):
    total = 0
    for row in range(1, n + 1):
        total += row
    return total

But using loops might get you thrown into a dungeon. Fortunately, one of the kids gets you started thinking like a Haskellian. They write the number of blocks needed to build a pyramid of height 8 as follows:

Then they add a little squiggly:

then say, notice anything?” Then it clicks!

or

And you realize that in general:

As cool as that looks, you do know that $n$ shouldn’t be negative, so you make a little adjustment:

Let’s program! Creating the folder ~/cmsi1010/lab08, and in it, a new file called im_so_sorry.py, with the following contents:

def blocks(n):
    if n <= 0:
        return 0
    else:
        return blocks(n - 1) + n

print(blocks(8))
print(blocks(0))
print(blocks(-1))
print(blocks(1))
print(blocks(838852))

Run it.

Add, commit, and push, too. 😀

It really works, but it might feel like what you did is unusual because it is very different from the loops you are used to. You replaced a loop by writing the function blocks to contain a call to blocks itself! Woah, functions that call themselves? This might remind you of famous images like this one:

This is pretty cool. In fact, this kind of thing has a name. The phenomenon of a function calling itself, and in fact any kind of thing that somehow, somewhere, containing smaller near-copies of itself, is called recursion. So a function that calls itself is a recursive function. And images that contain copies of themselves are called recursive images.

Important Vocabulary Time!

Notice the presence of the if statement inside the recursive blocks function. One branch of the if did not make a recursive call. This is called the base case. The base case is where the recursion stops. If you don’t have a base case, you’d “recurse forever.” Not a good look.

Always be clear, when writing a recursive function, to ensure a base case is there, and that every recursive call “makes progress toward the base case.”

Time to learn a little more Python. The if-else statement where each part is a single return can be written more compactly as:

def blocks(n):
    return 0 if n <= 0 else blocks(n - 1) + n

hemisphere = "North" if lat >= 0 else "South"

if lat >= 0:
    hemisphere = "North"
else:
    hemisphere = "South"

return 0 if n <= 0 else blocks(n - 1) + n

if n <= 0:
    return 0
else:
    return blocks(n - 1) + n

return "even" if n % 2 == 0 else "odd"

if n % 2 == 0:
    return "even"
else:
    return "odd"

Okay back to the recursion lab!

The blocks function is not even all that weird: all simple loops have recursive analogs. Here are some examples:

  factorial(4)
    = factorial(3) * 4
    = (factorial(2) * 3) * 4
    = ((factorial(1) * 2) * 3) * 4
    = (((factorial(0) * 1) * 2) * 3) * 4
    = (((1 * 1) * 2) * 3) * 4
    = ((1 * 2) * 3) * 4
    = (2 * 3) * 4
    = 6 * 4
    = 24

  is_palindrome("racecar")
    = ('r' == 'r') and is_palindrome("aceca")
    = true and is_palindrome("aceca")
    = is_palindrome("aceca")
    = ('a' == 'a') and is_palindrome("cec")
    = true and is_palindrome("cec")
    = is_palindrome("cec")
    = ('c' == 'c') and is_palindrome("a")
    = true and is_palindrome("a")
    = is_palindrome("a")
    = true

  sumOfDigits(-48729)
    = sumOfDigits(48279)
    = sumOfDigits(4827) + 9
    = (sumOfDigits(482) + 7) + 9
    = ((sumOfDigits(48) + 2) + 7) + 9
    = (((sumOfDigits(4) + 8) + 2) + 7) + 9
    = (((4 + 8) + 2) + 7) + 9
    = ((12 + 2) + 7) + 9
    = (14 + 7) + 9
    = 21 + 9
    = 30

In the challenges below, you will be asked to implement these functions in Python. To do so, you will need to identify base cases and figuring out how to break things down so you can take recursive steps. Here’s the information for the three examples above. Take this information as “hints” toward implementing the functions.

The // operator is new! It means divide then take the largest integer less than or equal to your result. So 5/2 == 2.5, 5//2 == 2, -5/2 == -2.5, and -5//2 == -3. The // operator is called the floor division operator.

Challenges

Now it’s your turn. Write recursive functions for each of the following, adding them to your im_so_sorry.py file. You should work with classmates to “come up with the algorithm” because recursive solutions are not as easy to visualize until you get lots of practice. But once to get it, it becomes oddly satisfying. BUT just because it is satisfying does not mean you should use recursion when simple loops suffice. (There are times, however, when recursion is simpler. We’ll explore such cases in the next lab. For now, just get your practice!)

• Sum of digits: Write a recursive function sum_of_digits(n) that returns the sum of the digits of a positive integer n. For example, sum_of_digits(1234) should return 10.
• Factorial: Write a recursive function factorial(n) that returns the factorial of a positive integer n. For example, factorial(5) should return 120.
• Is Palindrome: Write a recursive function is_palindrome(s) that returns True if the string s is a palindrome (reads the same forwards and backwards) and False otherwise. For example, is_palindrome("racecar") should return True, while is_palindrome("hello") should return False.
• Write a recursive function called print_count_down(n) that prints integers, one per line, from n down to 1, then prints BOOM. Hint: print_count_down(0) simply prints BOOM and print_count_down(n) for any positive integer prints n then calls print_count_down(n-1).

Further Study

Recursion is a pretty big topic. It’s been said most programmers can learn a for-loop or a while-loop in 10 minutes but it takes weeks to understand recursion. But fear not, there is a lot of help out there:

• I have some comprehensive notes on recursion, covering recursion in nature, art, language, music, and computer science. Most, but probably not all, of the page should be readable to you; just skip the parts that look too detailed (like the Efficiency Horrors and Memoization sections). However, please do watch the three videos by Vi Hart shown on that page.
• The book Think Python covers recursion in Chapters 5.8–5.13 and 6.5–6.9. Give those sections a read. Also browse the glossaries and end-of-chapter exercises for Chapters 5 and 6.

Summary

Recall Practice

Here are some questions useful for your spaced repetition learning. Many of the answers are not found on this page. Some will have popped up in lecture. Others will require you to do your own research.

1. What was the reaction of Haskellians to seeing loops in Python?
   Shock and dismay
2. What is the name of the phenomenon where a function calls itself?
   Recursion
3. What is a recursive function?
   A function that calls itself
4. What is a recursive image?
   An image that contains smaller copies of itself
5. What is the base case in a recursive function?
   The condition that stops the recursion, preventing it from going on forever.
6. The factorial of $n$ is $1 \times 2 \times \ldots \times n$. If writing a recursive factorial function, what is the base case? What is the recursive step?
   Base case: factorial(0) = 1. Recursive step: factorial(n - 1) * n.
7. What is 103 / 19, 103 // 19, and 103 % 19?
   103 / 19 = 5.421052631578948, 103 // 19 = 5, and 103 % 19 = 8.
8. When writing a recursive function to sum up the digits in a number, what are the base case and the recursive step?
   Base case: when $n < 10$, the sum is just $n$. Recursive step: sum_of_digits(n // 10)+ (n % 10).
9. When writing a recursive function to check if a string is a palindrome, what are the base case and the recursive step?
   Base case: string is empty or has length of 1, in which case you return True. Recursive step: first character and last character are the same AND the rest of the string (other than the first and last character) is a palindrome. In code: (s[0] == s[-1]) and is_palindrome(s[1:-1]).