序幕

什么是递归

递归，就是在运行的过程中调用自己。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

语言例子：

  1. 从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”

    img

  2. 一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓志铭，让未来的狗可以看到：“一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓志铭，让未来的狗可以看到：‘一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓志铭，让未来的狗可以看到……’”

  3. 大雄在房里，用时光电视看着从前的情况。电视画面中的那个时候，他正在房里，用时光电视，看着从前的情况。电视画面中的电视画面的那个时候，他正在房里，用时光电视，看着从前的情况……

代码例子：(最常见的就是斐波那契数列)

斐波那契数列 {1 1 2 3 5 8 13…n}

数学好的同学可能很容易就找到规律了：前两项之和等于第三项

如果让我们求出第n项是多少，那么我们就可以很简单写出对应的递归表达式了：Z = (n-2) + (n-1)

递归出口在本题目是需要有两个的，因为它是前两项加起来才得出第三项的值

1
2
3
4
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8

同样地，那么我们的递归出口可以写成这样：if(n==1) retrun 1 if(n==2) return 2

完整代码

1
2
3
4
5
6
7
8
def feibo(n):
	if n <= 2:
		return 1
	else:
		return feibo(n-1) + feibo(n-2)
    
for i in range(1,8):
	print(feibo(i))

递归优缺点

优点

  1. 简洁
  2. 在树的前序，中序，后序遍历算法中，递归的实现明显要比循环简单得多。
  3. 递归函数维持着一个保存每次递归调用当前状态的栈，允许函数获得子问题的结果后继续处理。

缺点

  1. 每次进入更深一层递归时，问题规模比上次递归都有所减少 。->效率

  2. 调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。->性能

    栈溢出解决办法

    1
    2
    3
    #修改递归深度的值
    import sys
    sys.setrecursionlimit(2000)

  1. 递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算。->效率

  2. 递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间。->效率

总结

递归思想说白了就是逆向思维，在大部分情况下，人们所想的是都是片面，也就是有局限性。逆向思维就是突破这个局限性，从另一方面去想怎么解决这个事情。

比如我们小时候耳熟能详的故事–司马光砸缸

关于司马光砸缸：
讲述了司马光砸坏水缸，救出同伴的故事。
在大部分情况下的人，当时所想的是如何让人脱离水，从而救出人。
我们通过逆向思维，想到也可以使水脱离人，从而脱救，于是把水缸砸坏，使水流光从而进行救助。