资源简介

(共20张PPT)
递归的概念与特征
The concept and characteristics of recursion
2022 JUNE 17th
讲课人：XXX
引 入
introduce
从前有座山，山上有座庙，庙里有个老和尚在讲故事，讲的是什么呢？从前有座山，山上有座庙……
coding is fun
什么是递归
What is recursion
#01
coding is fun
2022
JUNE 17th
Informatics Olympiad
2022
JUNE 17th
递归定义
实际上，递归的意思就是函数在执行时调用函数本身。
函数的递归调用是指一个函数在它的函数体内，直接或间接地调用它自身，称为递归调用。这种函数称为递归函数。
coding is fun
2022
JUNE 17th
实际问题
如何利用计算机编程求解一个正整数的阶乘呢？
coding is fun
2022
JUNE 17th
分析问题
设表示的阶乘，根据阶乘的定义可以得出。
coding is fun
因而，我们可以得到下面的表达式：
2022
JUNE 17th
分析问题
若的阶乘即已知，那么我们就可以直接用与相乘快速得到的阶乘。也就是。
因而，我们可以得到下面的表达式：
coding is fun
因而，我们可以得到下面的表达式：
2022
JUNE 17th
代码编写
coding is fun
def f(n):
if n <= 1:
return 1;
else:
return n * f(n – 1)

print(“请输入一个正整数: “, end = “”)
n = int(input())
print(“%d的阶乘是%d。” % (n, f(n)))
递归算法的条件
Conditions for recursive algorithms
#02
coding is fun
2022
JUNE 17th
Informatics Olympiad
2022
JUNE 17th
递归条件
使用递归解决的问题都可以通过同一套规则转化为比该问题更为简单的子问题，这套规则被称为该问题的递归定义或递归公式。
例如，在计算阶乘问题中，就是计算阶乘的递归公式。
coding is fun
2022
JUNE 17th
递归出口
经过不断缩小问题规模，问题最终能够得以解决。在刚才的问题中，的阶乘经过不断简化，最终转化为求解的阶乘，而的阶乘是我们已知的。 这种能直接得到结果，从而终止递归的情况，称为递归的边界条件。
coding is fun
利用递归解决问题
Use recursion to solve problems
#03
coding is fun
2022
JUNE 17th
Informatics Olympiad
问 题
problem
academic report
presentation
在第2章学习数组时我们知道，斐波纳奇数列指的是这样一个数列: 1,1,2,3,5,
8,13,21,34,...即从第3项开始，每一项都是前面两项的和。请根据同学们斐波纳奇数列的定义，小组之间进行讨论合作，用递归算法去求解斐波那契数列的第n项，编写计算斐波纳奇数列的程序， 并求出斐波那契数列第45项的结果。
coding is fun
2022
JUNE 17th
分析问题
如果用表示计算斐波纳奇数列的函数，那么根据定义我们可以知道，
当 或者 的时候 为 ，此时直接返回结果就可以。
与刚刚计算阶乘一样，我们可以得到以下表达式：
coding is fun
2022
JUNE 17th
适用情况
coding is fun
我们已经用递归算法解决了两个问题，那在什么情况下可以使用递归算法来解决问题的？
2022
JUNE 17th
适用情况
一、每次计算在规模上都有所缩小。
二、可以通过同一套规则(即相同的程序)转化为比该问题更为简单的子问题。比如:
三、问题的规模极小时必须用直接给出解答。比如:
coding is fun
总结
Summarize
#04
coding is fun
2022
JUNE 17th
Informatics Olympiad
内容梳理
递归的必要条件
递归的适用情况
递归的定义
函数的递归调用是指一个函数在它的函数体内，直接或间接地调用它自身，称为递归调用。这种函数称为递归函数。
确定递归条件
寻找递归出口
问题在规模小时能够直接得出答案
可以通过同一套规则转化为比该问题更为简单的子问题。
2022
JUNE 17th
Informatics Olympiad
作 业
Homework
academic report
presentation
年龄问题
有5个人做在一起，问第5个人多大了。他说比第四个人大2岁，问第四个人多大了，他说比第三个人大2岁，问第三个人多大了，他说比第二个人大2岁，问第二个人多大了，他说比第一个人大2岁，最后问第一个人，他说他10岁了。请大家用递归算法编写程序计算出第5个人多大了
coding is fun
2022
JUNE 17th
Informatics Olympiad
coding is fun

展开更多......

收起↑