关于函数递归的一些学习经验和技巧(申请加精)

18463102026

      在学习递归的时候第一感觉这个东西好难，不过立马我想到了他和我们高中数学中数列的递推公式是很类似的；
     下面我来给大家举一个例子：

   如图，我们知道了这个数列的第一项和相邻两项之间的关系，那怎么去求 a₁₀₀ 呢？（当然我们可以去求它的通项啦，但是我们现在不是学高中数学哦）那接下来给大家演示下怎么把这个通项公式转换为递推关系哦！

1. # 定义一个数列 an，表示第 n 个数的值
   
2. def a1(n):
   
3.     if n==1:
   
4.         return 2
   
5.     else :
   
6.         return a1(n-1)+2

复制代码

     我们仿照这个递推公式写出来了对应的函数，程序中第三行 if n== 1 对应的是递推公式 a₁=1；第六行的 return a(n-1)+2 就相当于递推公式的 a_n = a_n-1+2,从这里我们可以发现递推公式和递推这两有着不为人知的关系哦。
接下来为了大家的理解，那我们来一个有点难度例子哦！

     这是摘自某小学六年级的课后作业，让我们从中找到规律，求出第二十项，于是我们便开始找规律，最后发现从第三项开始每一项都是前两项的和，于是我们就一个一个的加到第二十项。小学我们是这么做的，那我们现在要用程序来求结果该怎么办呢？我们这里给大家写出来这个数列的通项公式：

     我们用高中数学写出来这个数列的递推公式以后就可以把他转换为函数了，函数如下：

1. # 定义一个数列 an，表示第 n 个数的值
   
2. def a2(n):
   
3.     if n==1 or n ==2:
   
4.         return 1
   
5.     else :
   
6.         return a2(n-1)+a2(n-2)

复制代码

     那我们可以初步的来总结下：
     1. 如果我们知道这个数列的一些开头的项和相邻项之间的关系的话，那么这个数列是确定的；并且能够写出该数列的递推公式；            
     2. 我们可以根据该数列的递推公式写出对应的函数。
     接下来为了更加深入理解，我们应该进行一些更加抽象的探讨。前面的数列指的是数字的排列，我们很容易能够理解，但是如果这个 “数列” 指的是做一些事情的步骤呢？那我们可以得到一些简单的猜想：
     1. 如果我们知道做一件事情的开头步骤和相邻步骤之间的关系，那我们可以按照这个指示完成该事情
     2. 我们可以根据得到的类似“递推关系”写出对应的函数
     说的好像有点抽象呢，我们直接来一个具体的例子把！比如说小甲鱼老师说过的汉诺塔例子，在汉诺塔中我们需要把 n 个饼子从 x 柱子移动到 z 柱子，其中 y 柱子是过渡的柱子，那接下来我们尝试着写一个类似“递推公式”表达式：

     有了递推公式以后我们可以写出对应的函数了：

1. def hanuo(n,x,y,z):
   
2.     if n == 1:
   
3.         print(x,'-->',z)
   
4.     else :
   
5.         hanuo(n-1,x,z,y)    # 这里表示从 x 移动到 y，所以 x 和 y 在边上，z 在中间
   
6.         print(x,'-->',z)
   
7.         hanuo(n-1,y,x,z)

复制代码

     在经过上面的理解后我应该会对递归有了一个比较深入的认识，接下来给大家演示了一个讲正整数转换为其二进制的“递推公式”以及其代码！

     代码：

1. # 正整数转换二进制的方法，和 bin() 函数一样
   
2. def bin_(n):
   
3.     if n == 1:
   
4.         return '0b'+str(n)
   
5.     else :
   
6.         return bin_(n//2)+str(n%2)

复制代码

     另外小甲鱼老师说过递归是很耗费内存的，最好能用其他方法代替，但是说实话用递归写出来的函数是真的短，所以 Python 内置了一个装饰器，一遍能够大大提升递归的运算速度，这里只要使用@lru_cache() 这一句就可以大大缩小运算时间，我们可以做一个实验，分别在有 @lru_cache() 和没有 @lru_cache() 的情况下计算 fibonacci(500)，你会发现很神奇的事情哦！方法如下：

1. from functools import lru_cache
   
2. @lru_cache()
   
3. def fibonacci(n):
   
4.     if n < 2:
   
5.         return n
   
6.     return fibonacci(n-2) + fibonacci(n-1)

复制代码

     参考连接1     参考连接2
@小甲鱼  @冬雪雪冬  @shuofxz @zltzlt

zltzlt

@小甲鱼

zltzlt

排版可以再调整一下

18463102026

   

小甲鱼

zltzlt 发表于 2019-12-11 21:59
@小甲鱼

不错！看得出很认真！

cnpzhlq

知识就是要融会贯通，向楼主学习

18463102026

cnpzhlq 发表于 2019-12-12 09:20
知识就是要融会贯通，向楼主学习

相互学习啦

不二如是

建议按照：申精#文章格式建议【官方指导】 修改格式

内容没问题，格式需要修改哦

magic_ant

居然有点看不懂了

Yvonne!

顶一个，学习^_^

zltzlt

做得不错，只是排版有点问题，帮你调整好了。

18463102026

zltzlt 发表于 2019-12-14 08:18
做得不错，只是排版有点问题，帮你调整好了。

感谢大佬
给你花花&#127801;&#127801;&#127801;

autist

膜拜学霸。顺便问一下@rlu_cache是干嘛的，还没学到

18463102026

autist 发表于 2019-12-15 18:35
膜拜学霸。顺便问一下@rlu_cache是干嘛的，还没学到

简单来说就是提高迭代速度，注意不能是参数不能是列表

Seawolf

谢谢分享