Page 121 - 高中 信息技术 选择性必修1 数据与数据结构

 5.1 迭代与递归

每个月的兔子对数组成数列：1，1，2，3，5，8，13，21，34，55，89，144，…
此数列也称为斐波那契数列。

探究活动

讨 论

分组讨论，日常学习、生活中有哪些活动、工作流程能体现迭代的思想？理解迭代算

法思想及其编程实现原理。

广东教育出版社
5.1.2 递归

1．递归的基本概念
若一个对象用自己来定义自己或部分地包含自己，则称这个对象是递归的；若一个过
程直接地或间接地调用自己，则称这个过程是递归过程。在程序设计中，函数直接调用函

数本身，称为直接递归调用；在函数中调用其他函数，其他函数又调用原函数，构成了函
数自身的间接调用，则称为间接递归调用。
2．递归在数学中的应用
在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简

单，于是人们想出另一种办法来描述这种数列，即通过初值及与前面临近几项之间的关系
来描述。要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，二是数
列间各项的关系。

例3：阶乘数列是由这样一组数组成：1，2，6，24，120，720，…，阶乘公式可以
表示为n! = n×(n-1)×(n-2)×…×1(n＞0)，数学上用这样的方式来描述阶乘数列：
1 (n=1)
n!=

n×(n-1)! (n>1)
下面的递归函数f可以实现求n!的值：
int f(int n) //定义递归函数f

{
if(n==1) return 1; //当n=1时返回1，结束递归
return n*f(n-1); //当n>1时返回n*f(n-1)，调用函数f来计算(n-1)!
}

这是递归函数的最简单形式，从中可以明显看出递归函数一般的写法特点：先处理一
些特殊情况（递归终结条件），再处理递归关系。
递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作
为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得

113113

21X2204.indd 113 2019/9/26 13:53:37