为什么会堆栈溢出问题？

在一个算法中，如果递归函数调用过多次数，那么就会导致堆栈溢出。

原因就是，操作系统会自动给每个进程分配一个最大栈空间2M，如果超过了这个上限，就会导致递归函数执行终止，所以就会报错。递归就像你一直在往一个空间里放东西，也就是一直在入栈，调用一次会把内存地址进行一次入栈，直到调用结束，才会将地址出栈。想一想，是不是如果调用次数过多，入栈的内存地址大于2M，就会引起程序报错呢？

同样的，如果你创建一个数组过大，会引起堆溢出，操作系统给每个进程分配的最大堆空间是4G，如果过大会导致堆溢出。

※（调用一个方法，在这个方法执行前都会将之前的内存地址（也就是调用点）入栈，等被调用的方法执行完将地址出栈，程序根据这个数据返回调用点）

解决递归函数堆栈溢出的方法就是尾递归：

尾递归就是在函数返回return时调用函数本身，而不使用其他表达式。这样执行的时候尾递归函数只会占用一个栈帧，就不会引起栈溢出。

下面是2个例子：

def fact(n):
    if n==1:
        return 1
    return n * fact(n - 1)

def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)

第一个就是递归函数；第二个就是优化后的尾递归。

 

 

很经典的递归算法例子-----【汉诺塔】：

汉诺塔是由三根杆子A，B，C组成的。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：每次只能移动一个圆盘；大盘不能叠在小盘上面。提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须尊循上述两条规则。问：如何移？最少要移动多少次？汉诺塔是根据一个传说形成的一个问题：

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

每次只能移动一个圆盘；

大盘不能叠在小盘上面。
 

以下是，答案及思路：

def move(n, a, b, c):
    if n == 1:
        print('move', a, '-->', c)
    else:
        move(n-1, a, c, b)  //先将初始柱A的前n-1个盘子借助目的柱C移动到借用柱B上
        move(1, a, b, c)   //将A柱剩下的一个最大盘子移动到目标C柱上
        move(n-1, b, a, c)  //最后将B柱上的n-1个盘子移动到目标C柱上

move(4, 'A', 'B', 'C')