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,

要計算正整數 N作為其參數的遞歸函數，

• 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.

  基本情況： N的結束情況等于一個特定的數字(通常為1或0)，在這種情況下，這將為我們提供特定的返回結果。

• 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).

  歸約步驟：對于該遞歸的每個步驟，我們將N- t用作其新參數(根據問題， t可以是任何常數)。

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

在這種情況下，正整數N稱為此遞歸的深度。

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

要計算序列 Seq的遞歸函數作為其參數，

• 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.

  基本情況：帶有Seq的結束情況等于一個空集(空列表/空字符串等)，在這種情況下，這將為我們提供特定的返回結果。

• 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.

  歸約步驟：對于此遞歸的每個步驟，我們都使用較短的Seq(通常將上一個元素移到上一個元素)作為其新參數。

問題1.倒數問題 (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.

假設我們正在研究一個火箭項目，并且我們想在火箭發射之前計算數量。 我們從5開始倒數，再從1開始倒數，然后打印“ Blastoff🚀”。 編寫有關它的遞歸函數。

問題2.創建斐波那契數列 (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.

假設我們給定索引n ，那么我們將返回此斐波那契數列的第n個元素。 編寫一個遞歸函數以計算第n個元素。 例如，索引n = 7將返回13。

問題3.計算最大公約數 (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!

兩個數的最大公除數(GCD)，也稱為最大公因數，是將兩個數除而無余的最大自然數d 。 讓我們編碼歐幾里得算法 (最常用的最古老算法之一)以找到GCD。 注意，該函數也應適用于負數 ，并且結果GCD始終為正 ！

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

編寫一個遞歸函數，該函數返回兩個數字的最大公約數。

4.計算列表的長度 (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.

查找一個返回列表中項目數的遞歸函數。 換句話說，編寫一個函數，為帶有遞歸的列表重新實現len函數。

5.反轉字符串 (5. Reverse a string)

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

假設我們有一個字符串，我們想通過遞歸來反轉它。 編寫一個函數來實現這一點。