递归及尾递归优化

1、递归介绍

递归简而言之就是自己调用自己。使用递归解决问题的核心就是分析出递归的模型，看这个问题能拆分出和自己类似的问题并且有一个递归出口。比如最简单的就5的阶乘，可以把它拆分成5*4!，然后求4!又可以调用自己，这种问题显然可以用递归解决，递归的出口就是求1！，可以直接返回1。用Python实现如下：

[python] 

​​view plain​​​

 ​​​copy​​

1. def fact(n):
2. if n==1:
3. return n
4. return n*fact(n - 1);
5. print(fact(5))

2、尾递归优化

在上面的求递归中，也有一定的缺点，假如说求1000!的阶乘，会出现栈溢出的问题，因为在函数执行中，没调用一个函数都会把当前函数的调用位置和内部变量保存在栈里面，由于栈的空间不是无限大（具体栈的最大空间还没有查找到），假如说调用层数过多，就是出现栈溢出的情况。

这个时候就可以用尾递归优化来解决，尾调用的概念非常简单，一句话就能说清楚，就是指某个函数的最后一步是调用另一个函数。

[python] 

​​view plain​​​

 ​​​copy​​

1. function f(x){
2. return g(x);
3. }

尾递归优化后的阶乘函数如下：

[python] 

​​view plain​​​

 ​​​copy​​

1. def fact(n):
2. return fact_iter(n,1);
3. def fact_iter(num, product):
4. if num == 1:
5. return product
6. return fact_iter(num - 1, num * product)
7. print(fact(5))
8. print(fact(1000))

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了。所以尾递归优化可以有效的防止栈溢出，但是尾递归优化需要编译器或者解释器的支持，遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化，所以，即使把上面的fact(n)函数改成尾递归方式，也会导致栈溢出。

3、汉诺塔问题

汉诺塔问题也是一个经典的递归问题，具体题目就不说了，这里分析思路。假设hanoi(n, a, b, c)实现把a上的n个盘子移到c上。

当只有一个盘子时，直接从A移动到C即可

如果有3个盘子，可以这样：

[cpp] 

​​view plain​​​

 ​​​copy​​

1. # A --> C
2. # A --> B
3. # C --> B
4. # A --> C
5. # B --> A
6. # B --> C
7. # A --> C

如果有很多盘子，我们分析一下该怎么移动，首先，我们需要把n-1个盘子移动到b中，才可以实现最简单的一步，把a中最大的盘子移动到c中，具体怎么转移到b中后面再讨论。移动最大的盘子后，a和c都可以看成是空的，接下来，把b看成是a，把a看成是b，把a中的n-1个盘子（这里的n是已经减1的n）移动到b后，又可以移动第二大的盘子。这显然是一个递归问题。

递归的出口就是n等于1，直接从a移动到c即可。

那么怎么接下来讨论，怎么把n-1个盘子移动到b，这不又是一个递归问题嘛！可以调用它自己呀，只不过需要把b看成是c，把c看成是b。所以代码如下：

[python] 

​​view plain​​​

 ​​​copy​​

1. def hanoi(n,a,b,c):
2. #只有一个盘子，直接移动
3. if n==1:
4. print(a,'->',c)
5. else:
6. #通过c把n-1个盘子移动到b
7. 1, a,c,b)
8. #移动最大的盘子
9. print(a,'->',c)
10. #通过a把n-1个盘子移动到c
11. 1, b,a,c)
12. hanoi(3,'A','B','C')

尾递归