Learning Objectives
- Introduce and explore the concept of recursion
- Experience writing recursive functions
Setup
From your CS 277 git directory, run the following:
git fetch release
git merge --allow-unrelated-histories release/lab_recursion -m "Merging initial lab_recursion files"
Upon a successful merge, your lab_recursion files are now in your lab_recursion directory.
You will only need to modify the following files:
recursion.py
Assignment Description
Recursion is a way of thinking about problems that allows the computer to do more of the heavy lifting for us. It is analogous to the mathematical definition of recursive functions, where you can define a function call in terms of calls to itself and basic arithmetic operations, but not in terms of loops.
Why recursion?
While being able to think recursively is one of the harder parts of computer science, it is also one of the most powerful. In fact, there are whole languages that entirely use recursion instead of loops, which, even though it may seem inefficient, leads to some very useful optimizations a compiler can make when dealing with such code. There are probably more problems in computer science that are simpler recursively than they are iteratively (using loops). Also, once you have a recursive algorithm, it is always possible to transform it into an iterative algorithm using a stack and a while loop. In this way, computer scientists can think about problems recursively, then use that recursive solution to make a fast iterative algorithm (and in the grand scheme of big-O notation, using recursion has little overhead compared to the rest of the running time). Here we’ll only ask you to do the first part.
Part 1: Recursive Exercises
How do I write recursively? Recursion just means calling a function within itself. This may sound crazy, but in fact it is not. Let’s take an iterative function to calculate the factorial of a number \(n\), \(n!\):
Iterative Example
def factorial(n):
result = 1
for i in range(n+1):
result = result * i
return result
Okay, so four lines of code. Pretty short and understandable. Now let’s look at a recursive version:
Recursive Example
def factorial(n):
if (n == 0): return 1
return (factorial(n-1) * n)
Only two lines of code! (Depending on whether you like putting your return statement on the same line.) Even on such a small problem, recursion helps us express ourselves more concisely. This definition also fits better with the mathematical definition:
A typical recursive function call consists of three parts. Let’s examine the function more closely to see them. Here’s the same code again, with more discussion.
Example
def factorial(n):
if (n == 0): # Here is our base case -- the smallest problem we can think of
return 1 # One we know the answer to and can return immediately
# with a fixed value
return (factorial(n-1) * n) # This is our recursive step. Here we are solving
# a smaller version of the same problem by
# breaking it down into a smaller sub-problem.
# In this case, we solve factorial by making the
# assumption that our function call will correctly
# compute the value (n-1)! and that we know n! is
# by definition [(n-1)! * n]
Exercises
You may not use any loops for this section! Try to think about the problem recursively: in terms of a base case, a smaller problem, and an incremental step to transform the smaller problem to the current problem.
Sum of Digits
Write a function sumDigits that takes as input a a non-negative int n and return the sum of its digits. Your solution must do this recursively (no loops are allowed).
HINT: Modulo (%) by 10 yields the rightmost digit (126 % 10 == 6), while divide (//) by 10 removes the rightmost digit (126 // 10 == 12). (Using // instead of / is floor division and will drop any decimals to get the closest integer)
int sumDigits(int n)
# INPUT:
# n is the given number whose digits we sum (int)
# OUTPUT:
# the sum of all the digits (int)
sumDigits(126) -> 1 + 2 + 6 -> 9
sumDigits(49) -> 4 + 9 -> 13
sumDigits(8) -> 8 -> 8
Triangle
One way of visualizing the sum of incrementing numbers is as a triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on:
* 1 block
* * 2 blocks
* * * 3 blocks
* * * * 4 blocks
............... n blocks
Write a function triangle_blocks that takes as input a non-negative integer n and returns the number of blocks in a triangle containing n rows.
int triangle_blocks(int rows)
# INPUT:
# rows is the number of rows in the triangle (int)
# OUTPUT:
# The number of blocks the triangle contains (int)
triangle(0) -> 0
triangle(1) -> 1
triangle(2) -> 3
triangle(5) -> 15
Note
These two examples were stolen from http://codingbat.com/java/Recursion-1. All credit goes to CodingBat exercises.
Palindrome
bool is_palindrome(string text)
Wrtie a function called is_palindrome that takes in a string called text and checks if it’s a palindrome. This is a classic CS Algorithms problem you’ll see all over the internet because it combines two key concepts: strings and recursion.
A palindrome is just a string that is the same when it’s reversed. For example, “racecar” backwards is still “racecar”. To approach the problem recursively, think about how you can shrink the string smaller at each step.
List Partitioning
One more thing recursion is great for is enumerating every possible combination of some problem. So one way of solving problems is using recursion to generate all of them and test a condition on them. This kind of combinatorial problem is hard the first time, but it gets easier going forward.
Write a funcion see if we can split a list into two smaller lists (or subsets) in a way that they both add up to the same sum. The two subsets combined have to include all items of a list and each item can only go to one of the two subsets. For example the list [3, 2, 3, 1, 3] can be split into [1, 3, 2] and [3, 3]. However [1, 1, 5] has no way of being split so we must return False.
bool can_partition(list[int] number_list)
# INPUT:
# number_list is the list we want to partition in half (list[int])
# OUTPUT:
# True If it's possible to partition into two equal value subsets (bool)
HINT: The simplest recursive solution here is to simultaneously attempt every possible partitioning. In order to do this, try thinking in terms of one element of the list at a time. Either you’re at a base case (no numbers left to partition) or deciding which set to add the current number to and moving on recursively.
HINT 2: A common tactic for more difficult recursive exercises is to use a ‘helper’ function which can pass along information necessary to solve the problem. If every recursive step assigns a single value to either of two smaller lists (subsets), what sort of information should be passed down recursively?