Section: 递回递回 | 13.2 递回

Section outline

Introduction
::导言

The Fibonacci is a famous recursive sequence named after the mathematician Leonardo Fibonacci. In the 12th century, Fibonacci developed an interesting problem involving rabbits. He began with a fictional pair (one male and one female) of baby rabbits. Fibonacci assumed that it would take one month for a baby rabbit to become an adult rabbit and reproduce. He also assumed that each pair of adult rabbits would produce a pair (one male and one female) of baby rabbits each month. Finally, he assumed that the rabbits would never die. Under these imaginary conditions, Fibonacci pondered how many rabbits would be present in one year. In solving this problem, he stumbled across the pattern now referred to as the Fibonacci sequence:
::Fibonacci是一个以数学家Leonardo Fibonacci命名的著名传生序列。在12世纪, Fibonacci 开发了一个与兔子有关的有趣问题。他首先对婴儿兔子做了一个虚构的配方(一男一女)。 Fibonacci 假设婴儿兔子要花一个月才能成为成年兔子和繁殖。他还假设每对成年兔子每月会产生一对(一男一女)婴儿兔子。最后,他假设兔子永远不会死。在这种假想的条件下, Fibonacci 思考了一年内将有多少兔子出现。在解决这个问题时,他偶然发现了现在称为Fibonacci 序列的模式:

\begin{aligned} 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . \end{aligned}

How can we represent the Fibonacci sequence using recursion?
::我们如何代表 Fibonacci 序列?

Recursion
::递回递回

A sequence is a list of numbers separated by commas. A sequence can be finite or infinite. If the sequence is infinite, the 1st few terms are followed by an ellipsis $\begin{aligned} (\dots) \end{aligned}$ , indicating that the pattern continues forever.
::序列是用逗号分隔的数字列表。序列可以是有限的, 也可以是无限的。如果序列是无限的, 几个词之后是省略号 , 表示该图案会永远持续下去。

An infinite sequence : $\begin{aligned} 1, 2, 3, 4, 5, \dots \end{aligned}$
::无限序列: 1,2,3,4,5,...

A finite sequence: $\begin{aligned} 2, 4, 6, 8 \end{aligned}$
::限定顺序:2,4,6,8

In general, you describe a sequence with subscripts that are used to index the terms. The $\begin{aligned} k^{t h} \end{aligned}$ term in the sequence is $\begin{aligned} a_{k} \end{aligned}$ .
::一般而言,您描述一个带有下标的序列,用于对术语进行索引。该序列中的 kth 术语为ak。

\begin{aligned} a_{1}, a_{2}, a_{3}, a_{4}, \dots, a_{k}, \dots \end{aligned}

::a1,a2,a3,a4,... ... ak,...

When you look at a pattern, there are many ways to describe it. You can describe patterns explicitly by stating how each term $\begin{aligned} a_{k} \end{aligned}$ is obtained from the term number $\begin{aligned} k \end{aligned}$ . You can also describe patterns recursively by stating how each new term $\begin{aligned} a_{k} \end{aligned}$ is calculated based on the previous term $\begin{aligned} a_{k - 1} \end{aligned}$ . Recursion defines an entire sequence based on the 1st term (or the 1st few terms) and the pattern between consecutive terms.
::当您查看一个模式时,有很多方法可以描述它。您可以明确描述模式,通过说明如何从数字 k 中获取每个术语。您还可以通过说明每个新术语ak是如何根据上一个术语ak - 1. 递解定义整个序列的,其依据是第一个术语(或第一个术语)和连续两个术语之间的模式。

When people see a pattern they seek to articulate how consecutive terms are related to one another. P atterns can be described with phrases like the ones below:
::当人们看到一种模式时,他们试图说明连续的术语是如何相互联系的。

Pattern	Recursive Description
$\begin{aligned} 3, 6, 12, 24, \dots \end{aligned}$	"Each term is twice as big as the previous term."
$\begin{aligned} 3, 6, 9, 12, \dots \end{aligned}$	"Each term is three more than the previous term."

Each phrase demonstrates recursive thinking , in that it defines each term as a function of the previous term.
::每个短语都体现了循环思维,因为它将每个术语定义为前一个术语的函数。

General Form of a Recursive Term
::递递递周期的一般形式

\begin{aligned} a_{k} = f (a_{k - 1}), a_{1} is the 1st term of the sequence . \end{aligned}

In some cases, a recursive formula can be a function of the previous two or three terms. Keep in mind that the downside of a recursively - defined sequence is that it is impossible to immediately know the 100th term without knowing the 99th term, which in turn might require knowing the 98th term, and so on.
::在某些情况下,递归公式可以是前两个或三个术语的函数。记住,一个递归定义序列的缺点是,如果不知道第99个术语,就无法立即知道第100个术语,而这反过来又可能需要知道第98个术语,等等。

The following video provides two examples of how to find the terms in a sequence given $\begin{aligned} a_{n} \end{aligned}$ , which is a recursive sequence formula:
::以下视频提供了两个例子,说明如何在给定的顺序中找到术语,这是一个循环序列公式:

Play, Learn, and Explore with Recursive Formulas:
::用递归公式播放、学习和探索:

Examples
::实例

Example 1
::例1

For the Fibonacci sequence, determine the 1st 11 terms and the sum of these terms.
::对于Fibonacci序列,确定第11个条件的第1个条件和这些条件的总和。

Solution:
::解决方案 :

\begin{aligned} 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143 \end{aligned}

Example 2
::例2

Write a recursive definition that fits the following sequence:
::写入符合以下顺序的递归定义 :

\begin{aligned} 3, 7, 11, 15, 18, \dots \end{aligned}

Solution:
::解决方案 :

To write a recursive definition for a sequence, you must define the pattern and state the 1st term. With this information, others would be able to replicate your sequence without having seen it for themselves.
::要写入序列的递归定义, 您必须定义模式, 并声明第一个术语。有了这个信息, 其他人可以复制您的序列, 而不用自己看到它。

\begin{aligned} a_{1} & = 3 \\ a_{k} & = a_{k - 1} + 4 \end{aligned}

::a1=3ak=ak-1+4

Example 3
::例3

What are the 1st nine terms of the sequence defined by $\begin{aligned} a_{1} = 1 \end{aligned}$ and $\begin{aligned} a_{k} = \frac{1}{a_{k - 1}} + 1 ? \end{aligned}$
::a1=1 和 ak=1ak-1+1 定义的序列的第一条九项条件是什么?

Solution:
::解决方案 :

\begin{aligned} 1, 2, \frac{3}{2}, \frac{5}{3}, \frac{8}{3}, \frac{13}{8}, \frac{21}{13}, \frac{34}{21}, \frac{55}{34} \end{aligned}

Ex ample 4
::例4

Recall the problem from the Introduction: How can we represent the Fibonacci sequence using recursion?
::回顾导言中的问题:我们如何利用循环来代表Fibonacci序列?

Solution:
::解决方案 :

The Fibonacci sequence is represented by the recursive definition:
::Fibonacci序列由递归定义所代表:

\begin{aligned} a_{1} & = 0 \\ a_{2} & = 1 \\ a_{k} & = a_{k - 2} + a_{k - 1} \end{aligned}

::a1=0a2=1ak=ak-2+ak-1

Example 5
::例5

The Lucas sequence is like the Fibonacci sequence, except that the starting numbers are 2 and 1 instead of 1 and 0. What are the 1st 10 terms of the Lucas sequence?
::卢卡斯的顺序和菲博纳奇的顺序相似除了起始数字是2和1,而不是1和0。卢卡斯顺序的第10个条件是什么?

Solution:
::解决方案 :

\begin{aligned} 2, 1, 3, 4, 7, 11, 18, 29, 47, 76 \end{aligned}

Example 6
::例6

Write the next five terms of the following sequence: $\begin{aligned} a_{1} = - 4, a_{2} = - 4, \end{aligned}$ and $\begin{aligned} a_{n} = 2 a_{n - 1} + a_{n - 2} \end{aligned}$ .
::写下以下顺序的下五个条件: a14, a24, 和 an=2an-1+an-2。

Solution:
::解决方案 :

\begin{aligned} a_{3} & = 2 (- 4) + (- 4) = - 12 \\ a_{4} & = 2 (- 12) + (- 4) = - 28 \\ a_{5} & = 2 (- 28) + (- 12) = - 68 \\ a_{6} & = 2 (- 68) + (- 28) = - 164 \\ a_{7} & = 2 (- 164) + (- 68) = - 396 \end{aligned}

So our answer is: -12, -28, -68, -164, and -396.
::a3=2(-4)+(-4)+(-4)12a4=2(-12)+(-4)28a5=2(-28)+(-12)28a5=2(-28)+(-12)68a6=2(-68)+(-28)164a7=2(-164)+(-68)+(-68)396。我们的回答是:-12,28,68,164和396。

Example 7
::例7

Consider the following pattern-generating rule:
::考虑下列模式生成规则:

If the last number is odd, multiply it by 3 and add 1.
::如果最后一个数字是奇数,则乘以3,再加1。

If the last number is even, divide the number by 2.
::如果最后一个数字是偶数,数字除以 2。

Repeat.
::重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复重复

Try a few different starting numbers and see if you can state what you think always happens.
::尝试几个不同的起始数字,看看能不能说明你认为总是发生的事情。

Solution:
::解决方案 :

You can choose any starting positive integer you like. Here are the sequences that start with 7 and 15.
::您可以选择任何您喜欢的起始正整数。这是从 7 和 15 开始的序列。

$\begin{aligned} 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, \dots \end{aligned}$

$\begin{aligned} 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, \dots \end{aligned}$

You could make the conjecture that any starting number will eventually lead to the repeating sequence 4, 2, 1.
::你可以推测任何起始数字最终都会导致重复序列4 2 1

This problem is called the Collatz conjecture, and is an unproven statement in mathematics. People have used computers to try all the numbers up to $\begin{aligned} 5 \times 2^{60}, \end{aligned}$ and many mathematicians believe it to be true, but since all natural numbers are infinite in number, this test does not constitute a proof.
::这个问题被称为科拉茨猜想,是数学中未经证实的语句。人们用计算机尝试所有数字,最高可达5x260,许多数学家认为这是真的,但是,由于所有自然数字都是无限的,这一测试不构成证据。

Summary
::摘要

If the sequence is infinite , the 1st few terms are followed by an ellipsis (...), indicating that the pattern continues forever.
::如果序列是无限的,那么在第一个条件之后就有一个省略号(.),表明这种模式将永远延续下去。

::如果序列是无限的,那么在第一个条件之后就有一个省略号(.),表明这种模式将永远延续下去。

Recursion defines an entire sequence based on the 1st term (or the 1st few terms) and the pattern between consecutive terms.
::递归根据第一个任期(或第一个任期)和连续两个任期之间的格局界定整个序列。

::递归根据第一个任期(或第一个任期)和连续两个任期之间的格局界定整个序列。

General Form of Recursive Term: $\begin{aligned} a_{k} = f (a_{k - 1}), a_{1} \end{aligned}$ is the 1st term of the sequence.
::递归期的一般形式:ak=f(ak-1),a1是序列的第一个条件。

Review
::回顾

Write a recursive definition for each of the following sequences:
::为下列顺序中的每一顺序写出递归定义:

1. $\begin{aligned} 3, 7, 11, 15, 19, \dots \end{aligned}$

2. $\begin{aligned} 3, 9, 27, 81, \dots \end{aligned}$

3. $\begin{aligned} 3, 6, 9, 12, 15, \dots \end{aligned}$

4. $\begin{aligned} 3, 6, 12, 24, 48, \dots \end{aligned}$

5. $\begin{aligned} 1, 4, 16, 64, \dots \end{aligned}$

6. Find the 1st six terms of the following sequence:
::6. 找出以下顺序的第1六个条件:

$\begin{aligned} b_{1} = 2 \end{aligned}$ , $\begin{aligned} b_{2} = 8 \end{aligned}$ , and $\begin{aligned} b_{k} = 6 b_{k - 1} - 4 b_{k - 2} \end{aligned}$
::b1=2, b2=8, bk=6bk-1-4bk-2

7. Find the 1st six terms of the following sequence:
::7. 找出以下顺序的第1六个条件:

$\begin{aligned} c_{1} = 4 \end{aligned}$ , $\begin{aligned} c_{2} = 18 \end{aligned}$ , and $\begin{aligned} c_{k} = 2 c_{k - 1} + 5 c_{k - 2} \end{aligned}$
::c1=4,c2=18,cck=2ck-1+5ck-2

Suppose the Fibonacci sequence started with 2 and 5:
::假设Fibonacci 序列以 2 和 5 开始 :

8. List the 1st 10 terms of the new sequence.
::8. 列出新顺序的第10个条件。

9. Find the sum of the 1st 10 terms of the new sequence.
::9. 找出新顺序第10个条件的总和。

Write a recursive definition for each of the following sequences:
::为下列顺序中的每一顺序写出递归定义:

10. $\begin{aligned} 1, 4, 13, 40, \dots \end{aligned}$

11. $\begin{aligned} 1, 5, 17, 53, \dots \end{aligned}$

12. $\begin{aligned} 2, 11, 56, 281, \dots \end{aligned}$

13. $\begin{aligned} 2, 3, 6, 18, 108, \dots \end{aligned}$

14 . $\begin{aligned} 4, 6, 11, 18, 30, \dots \end{aligned}$

15. $\begin{aligned} 7, 13, 40, 106, 292, \dots \end{aligned}$

Review (Answers )
::回顾(答复)

Please see the Appendix.
::请参看附录。

Section outline

Introduction ::导言

Recursion ::递回递回

General Form of a Recursive Term ::递递递周期的一般形式

Examples ::实例

Summary ::摘要

Review ::回顾

Review (Answers ) ::回顾(答复)

Introduction
::导言

Recursion
::递回递回

General Form of a Recursive Term
::递递递周期的一般形式

Examples
::实例

Summary
::摘要

Review
::回顾

Review (Answers )
::回顾(答复)