什么是python尾遞歸

本篇內容主要講解“什么是python尾遞歸”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“什么是python尾遞歸”吧!

遞歸是啥?

遞歸函數大家肯定寫過，學校上課的時候，估計最開始的例子就是斐波拉契數列了吧。例如：

int Fibonacci(n) {     if (n < 2) return n;     return Fibonacci(n - 1) + Fibonacci(n - 2); }

遞歸函數簡而言之就是在一個函數中，又“遞歸”調用自己。在寫遞歸函數的時候，需要注意的地方就是遞歸函數的結束條件。用遞歸函數確實能簡化很多算法的實現，比如常見的二叉樹遍歷等。但往往在寫遞歸函數的時候，最容易出現的問題就是所謂的“棧溢出”。

為什么會有“棧溢出”呢?因為函數調用的過程，都要借助“棧”這種存儲結構來保存運行時的一些狀態，比如函數調用過程中的變量拷貝，函數調用的地址等等。而“棧”往往存儲空間是有限的，當超過其存儲空間后，就會拋出著名的異常/錯誤“StackOverflowError”。

我們以一個簡單的加法為例，例如：

int sum(int n) {     if (n <= 1) return n;     return n + sum(n-1); }  std::cout << sum(100) << std::endl; std::cout << sum(1000000) << std::endl;

很簡答，編譯運行后，比較小的數字，能得到正確的答案，當數字擴大后，就會直接發生“segmentation fault”。

尾遞歸又是啥?

我得知這個概念，最開始還是因為很多年前一次面試，面試官問我“你知道什么是尾遞歸嗎?”，我以為是“偽”遞歸，難道是假的遞歸???當初我也是懵逼狀態(當初面試官忍住沒笑也是厲害了)。從“尾”字可看出來即若函數在尾巴的地方遞歸調用自己。上面的例子寫成尾遞歸，就變成了如下：

int tailsum(int n, int sum) {     if (n == 0) return sum;     return tailsum(n-1, sum+n); }

可以試試結果，計算從 1 加到 1000000，仍然是segmentation  fault。為什么呢?因為這種寫法，本質上還是有多層的函數嵌套調用，中間仍然有壓棧、出棧等占用了存儲空間(只不過能比前面的方法會省部分空間)。

尾遞歸優化

當你給編譯選項開了優化之后，見證奇跡的時刻到了，居然能算出正確結果。如圖所示：

C++ 默認 segmentation fault， 開啟編譯優化后，能正常計算結果。

原因就是因為編譯器幫助做了尾遞歸優化，可以打開匯編代碼看看(這里就不展示 C++的了)。后面我用大家比較熟悉的 JVM based 語言 Scala  來闡述這個優化過程。(好像 Java 的編譯器沒做這方面的優化，至少我實驗我本地 JDK8 是沒有的，不清楚最新版本的有木有)(scala  本身提供了一個注解幫助編譯器強制校驗是否能夠進行尾遞歸優化@tailrec)

object TailRecObject {     def tailSum(n: Int, sum: Int): Int = {         if (n == 0) return sum;         return tailSum(n-1, n+sum);    }     def main(args: Array[String]) {       println(tailSum(100, 0))       println(tailSum(1000000, 0))    }  }

結果如下圖所示，默認情況下 scalac 做了尾遞歸優化，能夠正確計算出結果，當通過 -g:notailcalls 編譯參數去掉尾遞歸優化后，就發生了  Exception in thread "main" java.lang.StackOverflowError了。

默認啟用尾遞歸優化正常計算結果，禁用尾遞歸優化則“StackOverflow”。

我們來看看生成的字節碼有什么不同。

包含尾遞歸優化的字節碼，直接 goto 循環。

禁用尾遞歸優化的字節碼，方法調用。

從上面可以看出，尾遞歸優化后，變成循環了(前面的 C++ 類似)。

到此，相信大家對“什么是python尾遞歸”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！