本期博客主要练习有关函数的递归方法,函数的递归有很多经典的例子,在这里我就写一下老师提供的几个题目,如果还想继续做相关题目的话,大家可以去力扣上面刷题。
注意:代码仅供参考,还请大家多多思考!
【填空8-1】采用递归思想,编程求斐波那契数列的指定项,指定项由键盘输入,请在代码的横线处补充。
斐波那契数列的公式是:
如下是斐波那契数列计算过程的动态图:
def fibonacci(n): if n > 2: return fibonacci(n-1) + fibonacci(n-2) elif n == 2: return 1 elif n == 1: return 1 x = eval(input("Input x=")) print(fibonacci(x))
'运行
它运行的结果是:
Input x=10
55
如果要显示斐波那契数列数列的前n项,n由键盘输入,我们可以这样修改以上程序来实现:
def fibonacci(n): if n > 2: return fibonacci(n-1) + fibonacci(n-2) elif n == 2: return 1 elif n == 1: return 1 x = eval(input("Input x=")) print(fibonacci(x)) for i in range(1, x + 1) : print(fibonacci(i), end = " ")
'运行
它运行的结果是:
Input x=10
55
1 1 2 3 5 8 13 21 34 55
【填空8-2】采用递归思想,以二分法查找有序列表的指定值,请在代码的横线处补充。
如下是二分法原理图:
def dichotomy(alist, item): if len(alist) == 0: # 查找范围为空返回找不到False return False else: midpoint = len(alist) // 2 # 求查找范围的中间点 if alist[midpoint] == item: return True else: # 待查值小于中间点,即缩小查找范围为中间点左半侧 if item < alist[midpoint]: return dichotomy(alist[: midpoint] , item) # 待查值大于中间点,即缩小查找范围为中间点右半侧 else: return dichotomy(alist[midpoint + 1:], item) testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42] print(dichotomy(testlist, 3)) print(dichotomy(testlist, 13))
'运行
它运行的结果是:
False True
'运行
【编程8-1】采用递归思想,将一个正整数倒序输出,例如给出正整数n=12345,即输出54321。
提示:首先输出这个数的个位数,然后再输出前面数字的个位数,直到之前没有数字为止。
首先递归表达式是:
rev_num = 0 base_pos = 1 def reversDigits(n): global rev_num global base_pos if(n > 0): reversDigits(int(n / 10)) rev_num += (n % 10) * base_pos base_pos *= 10 return rev_num n = eval(input("请给出正整数n=")) print("倒序输出后结果是:",reversDigits(n))
'运行
它运行的结果是:
请给出正整数n=12345
倒序输出后结果是:54321
本期内容就涉及到了函数递归的相关算法,我们首先要去理解它的原理才能更好更快的写出对应的程序,所以还是很有必要去看一下相关的数学原理。
除了上面所提到的题目,还有很多经典的例子,比如汉诺塔、数的阶乘等等,网上有很多,各种语言版本都有,大家可以去看一看,然后练一练,毕竟熟能生巧。