Advanced Python 1 | Recursion

Series: Advanced Python

Advanced Python 1 | Recursion

When something is specified in terms of itself, it is called recursion. The recursion gives us a new idea of how to solve a kind of problem and this gives us insights into the nature of computation. Basically, many of computational artifacts are naturally self-referential, for example:

  • File system
  • Fractal graph
  • Algorithms

Any recursion function consists of two parts:

  • Base case: the last case of the recursion. For every recursion, the last step must be the base case and it is going to return a specific value to us.
  • Reduction step: Assuming that the recursion works for smaller values of its argument, then use the function to compute a new return value.

Now think about the following examples:

To compute a recursion function of a positive integer N as its parameter,

  • Base case: The ending case with N equals a specific number (usually 1 or 0) and this will give us a specific return result under this condition.
  • Reduction step: For each of the steps of this recursion, we use N-t as its new parameter (t could be any constant based on the question).

In this case, the positive integer N is called the depth of this recursion.

To compute a recursion function of a sequence Seq as its parameter,

  • Base case: The ending case with Seq equals an empty set (empty list/empty string/etc.) and this will give us a specific return result under this condition.
  • Reduction step: For each of the steps of this recursion, we use a shorter Seq (usually moves one element from the previous one) as its new parameter.

Question 1. Counting-down Problem

Suppose we are working on a project of rocket and we want to count down numbers before the rocket blast off. We count down from 5 and after we count 1, we will then print “Blastoff 🚀”. Write a recursion function about it.

Question 2. Create a Fibonacci Sequence

Fibonacci sequence is a series in which each number is the sum of the two preceding numbers.

Suppose that we give an index n, then we are going to return the n-th element of this Fibonacci sequence. Write a recursion function to calculate the n-th element. For example, an index n = 7 will give back 13.

Question 3. Calculate the Greatest Common Divisor

The greatest common divisor (GCD), also called the greatest common factor, of two numbers is the largest natural number d that divides both numbers without a remainder. Let’s code up the Euclidean algorithm (one of the oldest algorithms in common use) to find the GCD. Note that this function should also work for negative numbers and the result GCD is always positive!

Write a recursive function that returns the greatest common divisor for two numbers.

4. Calculate the Length of a List

Find a recursive function that returns the number of items in a list. In other words, write a function that reimplements the len function for lists with recursion.

5. Reverse a string

Suppose we have a string and we would like to reverse it by recursion. Write a function to implement this.