python递归

一.递归

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

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

 #计算n的阶乘

 def fun(n):

     if n==1:

         return 1

     else:

         return fun(n-1)*n

 print (fun(10))

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

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

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

 def test1(n):

     return test2(n,1)

 def test2(n,product):

     if(n==1):

         return product

     else:

         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)

 def move(n,a,b,c):

     if n==1:

         print (a,'-->',c)

     else:

         move(n-1,a,c,b)

         move(1,a,b,c)

         move(n-1,b,a,c)

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

A --> C

A --> B

C --> B

A --> C

B --> A

B --> C

A --> C

巴特西

python递归

一.递归

二.python下实现汉诺塔问题

最新文章

热门文章