python递归

一.递归

　　（1）递归就是函数自己调用自己的过程；

　　（2）使用递归时，需要注意递归的出口，明确递归的终止条件。

1 #计算n的阶乘
2 def fun(n):
3     if n==1:
4         return 1
5     else:
6         return fun(n-1)*n
7 print (fun(10))

　　使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

　　解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。

尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

1 def test1(n):
2     return test2(n,1)
3 def test2(n,product):
4     if(n==1):
5         return product
6     else:
7         return test2(n-1,product*n)

二.python下实现汉诺塔问题

　　汉诺塔是印度一个古老传说的益智玩具。汉诺塔的移动也可以看做是递归函数。

　　我们对柱子编号为a, b, c，将所有圆盘从a移到c可以描述为：
　　　　如果a只有一个圆盘，可以直接移动到c；
　　　　如果a有N个圆盘，可以看成a有1个圆盘（底盘） + (N-1)个圆盘，首先需要把 (N-1) 个圆盘移动到 b，然后，将 a的最后一个圆盘移动到c，再将b的(N-1)个圆盘移动到c。
　　请编写一个函数，给定输入 n, a, b, c，打印出移动的步骤：
　　move(n, a, b, c)

1 def move(n,a,b,c):
2     if n==1:
3         print (a,'-->',c)
4     else:
5         move(n-1,a,c,b)
6         move(1,a,b,c)
7         move(n-1,b,a,c)
8 move(3,'A','B','C')

A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C