Recursion and Tree Recursion

Q1: Subsequences

A subsequence of a sequence S is a subset of elements from S, in the same order they appear in S. Consider the list [1, 2, 3]. Here are a few of it’s subsequences [], [1, 3], [2], and [1, 2, 3].

Write a function that takes in a list and returns all possible subsequences of that list. The subsequences should be returned as a list of lists, where each nested list is a subsequence of the original input.

Q2: Convert Link

Write a function convert_link that takes in a linked list and returns the sequence as a Python list. You may assume that the input list is shallow; that is none of the elements is another linked list.

Try to find both an iterative and recursive solution for this problem!

It is easy to solve this problem iteratively. All we have to do is to make a list to store these nodes we have visited while we iterating this linklist.

Accounts

Q2: Retirement

Add a time_to_retire method to the Account class. This method takes in an amount and returns how many years the holder would need to wait in order for the current balance to grow to at least amount, assuming that the bank adds balance times the interest rate to the total balance at the end of every year.

The description tells us that: We will add our balance every year, so when may we retire? Both the math and code are simple.

Q1: Generate Permutations

Given a sequence of unique elements, a permutation of the sequence is a list containing the elements of the sequence in some arbitrary order. For example, [2, 1, 3], [1, 3, 2], and [3, 2, 1] are some of the permutations of the sequence [1, 2, 3].

Implement gen_perms, a generator function that takes in a sequence seq and returns a generator that yields all permutations of seq. For this question, assume that seq will not be empty.

Mutability

Write a function which takes in a list lst, an argument entry, and another argument elem. This function will check through each item in lst to see if it is equal to entry. Upon finding an item equal to entry, the function should modify the list by placing elem into lst right after the item. At the end of the function, the modified list should be returned.

See the doctests for examples on how this function is utilized.

Mobiles

Q2: Weights

Implement the planet data abstraction by completing the planet constructor and the size selector so that a planet is represented using a two-element list where the first element is the string 'planet' and the second element is its size.

From the description, we can know what is planet. It is a ['planet', size]. Then we can take a look at the mobile function, the solution is quite similar.

Lists

Q1: Factors List

Write factors_list, which takes a number n and returns a list of its factors in ascending order.

We can know such a basic mathematical fact: the factor of a number can only be up to half of it (when the number is even). So we use for i in range(1, n // 2 + 1)

Intro

I find it really interesting to solve recursive problems. I like this way of solving problems, the code is concise and intuitive, which is why I wrote this blog.

📒 How to solve a recursive problem ?

1. What is the base case ?
2. How to break down the current problem into simpler ones ?

Later, I will follow this idea to solve the recursion problem in this lab.

Recursion

Q2: Summation

Write a recursive implementation of summation, which takes a positive integer n and a function term. It applies term to every number from 1 to n including n and returns the sum.

hw03. Recursion, Tree Recursion

Q1: Num eights

Write a recursive function num_eights that takes a positive integer pos and returns the number of times the digit 8 appears in pos.

Important: Use recursion; the tests will fail if you use any assignment statements. (You can however use function definitions if you so wish.)

It is easy to think of the answer to this question, for we have seen a similar one in lecture. We can split the pos into all_bust_last and last. When we arrive at the base case, we just need to check if it is equals to 8. Because we can not use = in this problem, we need to use function instead.

Intro

I found that the windows management built in macOS is difficult to use. As a result, I always using my mouse to move and resize my window, which is less efficient. We should keep our hands on the keyboard as much as possible. After finishing the MIT-Missing-Semester, I came across the hammerspoon tool. I really like this one :)

What is hammerspoon ?

According to the official site’s introduction, hammerspoon is a tool for powerful automation of OS X, which is just a bridge between the operating system and a Lua scripting engine. The windows management is kind of automation.

hw02. Higher Order Functions

Q1: Product

The summation(n, term) function from the higher-order functions lecture adds up term(1) + ... + term(n). Write a similar function called product that returns term(1) * ... * term(n).

This problem is quite easy, we just need to use * instead of +. The logic is similar to summation(n, term) function in the lecture.

Remember to set ans = 1 at first, after all, 0 * any numbers is always equal to 0 🤗

hw01. Control

Q1. Welcome Forms

Skip :)

Q2. A Plus Abs B

Fill in the blanks in the following function for adding a to the absolute value of b, without calling abs. You may not modify any of the provided code other than the two blanks.

This problem is easy if we know that we can bind names to functions. In this problem:

• When b < 0, a + abs(b) = a - b, so we should use sub
• When b > 0, a + abs(b) = a + b, so we should use add