Discuss / Python / 递归函数

递归函数

Topic source

七月上行

#1 Created at ... [Delete] [Delete and Lock User]

在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。 解决递归调用栈溢出的方法是通过尾递归优化,事实上尾递归和循环的效果是一样的,所以,把循环看成是一种特殊的尾递归函数也是可以的。

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

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

无论有多少层盘,都把上面的n-1层等效为一个整盘挪到中间的B柱,然后把最下面一个挪到C柱,然后再移动那n-1层整盘到C柱。 if n == 1: print(a, '-->', c) else: move(n-1, a, c, b) move(1, a, b, c) move(n-1, b, c, a)

不错哦 理解的很到位


  • 1

Reply