一、前言
本期博客主要练习有关函数的递归方法，函数的递归有很多经典的例子，在这里我就写一下老师提供的几个题目，如果还想继续做相关题目的话，大家可以去力扣上面刷题。
注意：代码仅供参考，还请大家多多思考！
二、我的环境
- 电脑系统：Windows 11
- 语言版本：Python 3.10.4
- 编译器：VSCode
三、实验目的与要求
- 掌握函数递归的定义和使用方法
- 理解实验中的经典递归算法思想
四、实验任务
1、程序填空
【填空8-1】采用递归思想，编程求斐波那契数列的指定项，指定项由键盘输入，请在代码的横线处补充。
斐波那契数列的公式是：
如下是斐波那契数列计算过程的动态图：
deffibonacci(n): ifn>2: returnfibonacci(n-1) +fibonacci(n-2) elifn==2: return1elifn==1: return1x=eval(input("Input x=")) print(fibonacci(x))
它运行的结果是：
Inputx=1055
如果要显示斐波那契数列数列的前n项，n由键盘输入，我们可以这样修改以上程序来实现：
deffibonacci(n): ifn>2: returnfibonacci(n-1) +fibonacci(n-2) elifn==2: return1elifn==1: return1x=eval(input("Input x=")) print(fibonacci(x)) foriinrange(1, x+1) : print(fibonacci(i), end=" ")
它运行的结果是：
Inputx=105511235813213455
【填空8-2】采用递归思想，以二分法查找有序列表的指定值，请在代码的横线处补充。
如下是二分法原理图：
defdichotomy(alist, item): iflen(alist) ==0: # 查找范围为空返回找不到FalsereturnFalseelse: midpoint=len(alist) //2# 求查找范围的中间点ifalist[midpoint] ==item: returnTrueelse: # 待查值小于中间点，即缩小查找范围为中间点左半侧ifitem<alist[midpoint]: returndichotomy(alist[: midpoint] , item) # 待查值大于中间点，即缩小查找范围为中间点右半侧else: returndichotomy(alist[midpoint+1:], item) testlist= [0, 1, 2, 8, 13, 17, 19, 32, 42] print(dichotomy(testlist, 3)) print(dichotomy(testlist, 13))
它运行的结果是：
FalseTrue
2、程序编程
【编程8-1】采用递归思想,将一个正整数倒序输出,例如给出正整数n=12345,即输出54321。
提示:首先输出这个数的个位数，然后再输出前面数字的个位数，直到之前没有数字为止。
首先递归表达式是：
rev_num=0base_pos=1defreversDigits(n): globalrev_numglobalbase_posif(n>0): reversDigits(int(n/10)) rev_num+= (n%10) *base_posbase_pos*=10returnrev_numn=eval(input("请给出正整数n=")) print("倒序输出后结果是：",reversDigits(n))
它运行的结果是：
请给出正整数n=12345倒序输出后结果是：54321
五、最后我想说
本期内容就涉及到了函数递归的相关算法，我们首先要去理解它的原理才能更好更快的写出对应的程序，所以还是很有必要去看一下相关的数学原理。
除了上面所提到的题目，还有很多经典的例子，比如汉诺塔、数的阶乘等等，网上有很多，各种语言版本都有，大家可以去看一看，然后练一练，毕竟熟能生巧。
