可以看到, 一般遞歸, 每一級遞歸都需要調(diào)用函數(shù), 會創(chuàng)建新的棧,

隨著遞歸深度的增加, 創(chuàng)建的棧越來越多, 造成爆棧:boom:

尾遞歸

尾遞歸基于函數(shù)的尾調(diào)用 , 每一級調(diào)用直接返回函數(shù)的返回值更新調(diào)用棧,而不用創(chuàng)建新的調(diào)用棧, 類似迭代的實現(xiàn), 時間和空間上均優(yōu)化了一般遞歸!

def tail_recursion(n, total=0):    if n == 0:        return total    else:        return tail_recursion(n-1, total+n)

執(zhí)行：

tail_recursion(5)tail_recursion(4, 5)tail_recursion(3, 9)tail_recursion(2, 12)tail_recursion(1, 14)tail_recursion(0, 15)15

可以看到, 每一級遞歸的函數(shù)調(diào)用變成"線性"的形式.

深入理解尾遞歸

 2/7   首頁 上一頁 1 2 3 4 5 6 下一頁 尾頁