课程： 12.1 递回 | The Way To Learn

章节大纲

选择节常规

折叠展开
常规

全部折叠展开全部
- 选择活动新闻通告
  
  新闻通告讨论区

递回递回

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 obtained from the previous term $\begin{aligned} a_{k - 1} \end{aligned}$ . Recursion defines an entire based on the first term and the pattern between consecutive terms. The Fibonacci sequence is a famous recursive sequence, but how is it represented using recursion?
::当您查看一个模式时,有很多方法可以描述它。您可以通过说明从数字k中获取的每个术语的公式来明确描述模式。您也可以通过说明从上一个术语中获取的每个新术语的公式的递归性来描述模式。递解根据第一个术语和连续两个术语之间的模式来定义一个整体。 Fibonacci 序列是一个著名的递归序列, 但是它是如何用递归来表示的呢 ?

$\begin{aligned} 0, 1, 1, 3, 5, 8, 13, 21, 34, \dots \end{aligned}$

Finding Terms with Recursion
::与递归的查找条件

When most people see a pattern they see how consecutive terms are related to one another. You might describe patterns 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 is a sign of recursive thinking that defines each term as a function of the previous term.
::每个短语都是循环思维的象征,将每个术语界定为前一个术语的函数。

\begin{aligned} a_{k} = f (a_{k - 1}) \end{aligned}

::k=f( ak- 1)

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 $\begin{aligned} 100^{t h} \end{aligned}$ term without knowing the $\begin{aligned} 99^{t h} \end{aligned}$ term.
::在某些情况下,递归公式可以是前两个或三个术语的函数。记住,一个递归定义序列的缺点是,在不知道第99个术语的情况下,不可能立即知道第100个术语。

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

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

The first term is : $\begin{aligned} a_{1} = 3 \end{aligned}$
::第一个学期是:a1=3

Notice that each of the following terms increases by 4 so the recursive piece of the sequence is : $\begin{aligned} a_{k} = a_{k - 1} + 4 \end{aligned}$ . Putting the two together gives you the recursive definition of the sequence:
::注意以下每个术语增加 4, 所以序列的递归部分是 : ak=ak- 1+ 4。将两个词组合起来, 给您带来序列的递归定义 :

$\begin{aligned} a_{1} = 3 \end{aligned}$
::a1=3

$\begin{aligned} a_{k} = a_{k - 1} + 4 \end{aligned}$
::ak=ak - 1+4 亚克=ak - 1+4

A recursive definition must always have two parts, the base case(the starting number) and the recursive case (the pattern to get more terms). Note that the base case may include more than one statement as is the case with the Fibonacci sequence.
::递归性定义必须始终有两个部分,即基数(起始数)和递归性(获得更多术语的模式),注意基数可能包含一个以上的语句,如Fibonacci序列。

Examples
::实例

Example 1
::例1

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

$\begin{aligned} a_{1} = 0 \end{aligned}$
::a1=0

$\begin{aligned} a_{2} = 1 \end{aligned}$
::a2=1

$\begin{aligned} a_{k} = a_{k - 2} + a_{k - 1} \end{aligned}$
::ak=ak - 2+ak - 1

The first eleven terms and the sum of these terms is:
::头十一个任期和这些任期的总和如下:

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

Example 2
::例2

What are the first nine terms of the sequence defined by:
::序列的顺序前九个条件是什么:

$\begin{aligned} a_{1} = 1 \end{aligned}$
::a1=1

$\begin{aligned} a_{k} = \frac{1}{a_{k - 1}} + 1 ? \end{aligned}$
::ak=1ak- 1+1 吗 ?

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

Example 3
::例3

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 first ten terms of the Lucas sequence?
::卢卡斯的顺序和菲博纳奇的顺序相似除了起始数字是2和1,而不是1和0。卢卡斯的顺序的前10个条件是什么?

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

Example 4
::例4

Zeckendorf’s Theorem states that every positive integer can be represented uniquely as a sum of nonconsecutive Fibonacci numbers. What is the Zeckendorf representation of the number 50 and the number 100?
::Zeckendorf的理论指出,每个正整数都可以被独到地代表为非连续的Fibonacci数字的总和。 Zeckendorf的50和100数字代表是什么?

$\begin{aligned} 50 = 34 + 13 + 3; 100 = 89 + 8 + 3 \end{aligned}$

Example 5
::例5

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.
::尝试几个不同的起始数字,看看能不能说明你认为总是发生的事情。

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.
::这个问题被称为Collatz Conjecture(Collatz Conjecture ) , 并且是数学中未经证实的语句。人们用计算机尝试所有数字,最高可达5x260, 并且许多数学家都相信这是真的,但是,由于所有自然数字都是无限的,这一测试并不构成证据。

Summary

Recursion defines an entire sequence based on the first term and the pattern between consecutive terms.
::递归根据第一个任期和连续任期之间的格局界定了整个顺序。

Recursive thinking involves describing patterns as a function of the previous term(s).
$\begin{aligned} a_{k} = f (a_{k - 1}) \end{aligned}$
::递归思维是指将模式描述为前一任期的函数。 ak=f( ak- 1)

A recursive definition must have two parts: the base case (the starting number) and the recursive case (the pattern to get more terms).
::循环定义必须有两个部分:基本情况(起始数)和循环情况(获得更多术语的模式)。

Review
::回顾

Write a recursive definition for each of the following sequences.
::a 为以下顺序中的每个序列编写递归定义。

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 first 6 terms of the following sequence:
::6. 确定以下顺序的前6个条件:

$\begin{aligned} b_{1} = 2 \end{aligned}$
::b1=2

$\begin{aligned} b_{2} = 8 \end{aligned}$
::b2=8 (b2=8)

$\begin{aligned} b_{k} = 6 b_{k - 1} - 4 b_{k - 2} \end{aligned}$
::bk=6bk-1-4bk-2

7. Find the first 6 terms of the following sequence:
::7. 确定以下顺序的前6个条件:

$\begin{aligned} c_{1} = 4 \end{aligned}$
::c1=4

$\begin{aligned} c_{2} = 18 \end{aligned}$
::c2=18 (c2=18)

$\begin{aligned} c_{k} = 2 c_{k - 1} + 5 c_{k - 2} \end{aligned}$
::ck=2ck-1+5c-2

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

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

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

Write a recursive definition for each of the following sequences. These are trickier!
::为以下序列中的每一序列写入递归定义。它们是更狡猾的 !

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)
::回顾(答复)

Click to see the answer key or go to the Table of Contents and click on the Answer Key under the 'Other Versions' option.
::单击可查看答题键, 或转到目录中, 单击“ 其他版本” 选项下的答题键。

章节大纲

常规

递回递回

Finding Terms with Recursion ::与递归的查找条件

Examples ::实例

Example 1 ::例1

Example 2 ::例2

Example 3 ::例3

Example 4 ::例4

Example 5 ::例5

Review ::回顾

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