CS111 Recursion Lab
Published:
Setup
Access the starter code here. You will need to copy and paste the code into your own file.
Solve the following exercises with a partner.
Exercise 0: Palindromes
We discussed this example together. Re-implement the code and discuss the questions with a partner to check your understanding.
A palindrome is a word or phrase that reads the same forwards and backwards. For instance, “racecar” and “madam” are palindromes.
Write a recursive function that checks whether a string is a palindrome.
- What is the base case?
- If a string has length n, how many recursive calls will there be?
Exercise 1: Triangular numbers
For $n\geq 1$, the $n$th triangular number is the sum $1 + …. + n$. For instance, the 5th triangular number is $15 = 1 + 2 + 3 + 4 + 5$. Write a function to recursively compute the $n$th triangular number.
Hint: If $T_k$ is the $k$th triangular number, how would you write the $(k+1)$st triangular number, $T_{k+1}$?
- What is the base case?
- How is this function different from
factorial_recursive()
that we talked about at the start of class?
Exercise 2: Reversing a string
I want to convert a string to be read backwards. For instance, “hello” should become “olleh”.
Write a function to do this recursively.
- What is the base case? (Hint: what is the reverse of
"a"
? What about of""
?) - What is the recursive case?
Exercise 3: Nested list target matching
Suppose that I have a nested list. Each entry in the list is either an integer or another list. For instance, [[1, 2, 3], 4, [5, 6, 7], 8]
is a nested list with 2 levels. We want to write a function nested_list(lst, target)
that checks whether a target integer is in the list or any of its sub-lists. For instance, the function would return True for the example list with target=1 or target=4, but false for target=9.
- Look at the code for
nested_list_depth_2
. This is an iterative function (i.e., uses afor
orwhile
loop) that checks whether a target integer is in a nested list with up to two levels.- How would you have to modify this function to solve the problem for a list with up to 3 levels, e.g.,
[1, [2, [3, 4], 5], 6]
? Is this modification scalable for lists that are arbitrarily deep?
- How would you have to modify this function to solve the problem for a list with up to 3 levels, e.g.,
- Write a recursive function that checks whether a target integer is in a nested list of any depth. Hint: You are allowed to use a loop, as long as you also use recursion.
- What is the base case? (Hint: What would a function called
nested_list_depth_1
look like?) - How many recursive calls are there for the input
[1, [2, 3], [4, [5, 6, [7, 8], 9], [10, 11]], 12]
?
Exercise 4: Fibonacci sequence
The Fibonacci sequence is defined as 0, 1, 1, 2, 3, 5, 8, 13, …. That is, given the starting values $F_0$=0 and $F_1$=1, the nth Fibonacci number for $n\geq 2$ is $F_n=F_{n-1} + F_{n-2}$.
Write a recursive function to compute the nth Fibonacci number, for $n\geq 0$.
Hint: You may want to include more than one base case.
Hint: You may want to include multiple recursive calls.
Note: Writing this function is a good way to practice recursion, but it turns out this function is very slow when $n$ is too large (on Anna’s computer, it noticeably slows down when $n>25$ and stops working when $n>35$). You will learn more on Wednesday about why this is, and what is a better way to compute the Fibonacci numbers!
Exercise 5: Binary to decimal (Challenge!)
Behind the scenes, computer code is compiled to binary, i.e., base-2 numbers that are strings of 0’s and 1’s. For instance, "10"
represents 2 and "101"
represents 5.
Recall that we can decompose decimal (base 10) numbers to be written as powers of 10. For instance, 2345 can be written as $2\times 10^3 + 3\times 10^2 + 4 \times 10^1 + 5\times 10^0$.
Likewise, we can convert a binary string to base 10 by writing it as a sum of powers of 2. For instance,
"10"
$= 1 \times 2^1 + 0 \times 2^0 = 2$"101"
$= 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0$"1010111"
$= 1\times 2^6 + 0 \times 2^5 + 1\times 2^4 + 0 \times 2^3 + 1\times 2^2 + 1\times 2^1 + 1\times 2^0 = 64 + 16 + 4 + 2 + 1 = 87$
Write a function to convert a binary string of 0’s and 1’s to a base-ten integer using recursion.
- What is the base case? (Hint: What numbers are written the same in base 10 and base 2?)
- What is the recursive call? (How are you making progress towards the base case?)
- For a binary string of length n, how many recursive calls will you do?