lab_recursion

Learning Objectives

• Introduce and explore the concept of recursion
• Experience writing recursive functions

Submission Instructions

Using the Prairielearn workspace, test and save your solution to the following exercises. (You are welcome to download and work on the files locally but they must be re-uploaded or copied over to the workspace for submission).

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!\):

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:

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.

def factorial(n):

    # Here is our base case -- the smallest possible input to n
    # And one that we can solve directly with a fixed value
    if (n == 0): 
        return 1 
    
    # This is our recursive and combination steps in one!
    # The recursive step is that we are solving
    # a smaller version of the same problem by 
    # breaking it down into a smaller sub-problem.
    # (It is easier to solve (n-1)! than n!)
    # Our combination step is that if we know the value 
    # (n-1)! then to get n! we just need to take [(n-1)! * n]
    return (factorial(n-1) * n) 

Exercises

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 dividing (//) 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

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?