python递归函数用递归和非递归的方式分别实现pop函数

来源：蜘蛛抓取(WebSpider) 时间：2018-12-12 14:01 标签： python递归函数

　　定义：程序调用自身的编程技巧称为递归（ recursion）递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合一般来说，递归需要有边界条件、递归前进段和递归返回段当边界条件不满足时，递归前进；当边界条件满足时递归返回。

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

　　定义：迭代是重复反馈过程的活动其目的通常是为了逼近所需目标或结果。每一次对过程的重复稱为一次“迭代”而每一次迭代得到的结果会作为下一次迭代的初始值。

　　在函数内部可以调用其他函数。如果一个函数在内部调用自身本身这个函数就是递归函数。举个例子我们来计算阶乘n! = 1 x 2 x 3 x ... x n，用函数fact(n)表示可以看出：

fact(n-1)，只有n=1时需要特殊处理于是，fact(n)用递归的方式写出来就是：

　　上面就是一个递归函数可以试试：

　　如果我们计算fact(5)，可以根据函数定义看到计算过程如下：

　　递归函数的优点是定义简单逻辑清晰。理论上所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰

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

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

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

　　上面的fact(n)函数由于return n * fact(n - 1)引入了乘法表达式所以就不是尾递归了。要改成尾递归方式需要多一点代码，主要是要把每一步的乘积传入到递归函数中：

product在函数调用前就会被计算不影响函数调用。

　　尾递归调用时如果做了优化，栈不会增长因此，无论多少次调用也不会导致栈溢出

　　遗憾的是，大多数编程语言没有针对尾递归莋优化python递归函数解释器也没有做优化，所以即使把上面的fact(n)函数改成尾递归方式，也会导致栈溢出

　　使用递归函数的优点是逻辑简單清晰，缺点是过深的调用会导致栈溢出

　　针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的没有循环语句的编程语言只能通过尾递归实现循环。

　　python递归函数标准的解释器没有针对尾递归做优化任何递归函数都存在栈溢出的问题。

　　汉诺塔的移动可以用递归函数非常简单地实现

　　请编写move(n, a, b, c)函数，它接收参数n表示3个柱子A、B、C中第1个柱子A的盘子数量，然后打印出紦所有盘子从A借助B移动到C的方法

我要回帖

更多关于 python递归函数 的文章

 

随机推荐