天天看點

遞歸和尾遞歸

c允許一個函數調用其本身,這種調用過程被稱作遞歸(recursion)。

最簡單的遞歸形式是把遞歸調用語句放在函數結尾即恰在return語句之前。這種形式被稱作尾遞歸或者結尾遞歸,因為遞歸調用出現在函數尾部。由于為遞歸的作用相當于一條循環語句,是以它是最簡單的遞歸形式。

遞歸中必須包含可以終止遞歸調用的語句!

遞歸的有點在于為某些程式設計問題提供了最簡單的方法,而缺點是一些遞歸算法會很快耗盡計算機的記憶體資源。同時,使用遞歸的程式難于閱讀和維護

咨詢了一下專家,确實對于“尾遞歸”的情況,也就是說函數體中用到的變量不需要棧儲存,gcc

-o2是可以進行優化的,會将其展開成循環,但如果遞歸函數中有分支就不行,比如路徑周遊的實作。有分支就要儲存條件變量,就需要壓棧,這種情況就展不

開。實際編碼中絕大多數都是這種情況。

遞歸和尾遞歸

部門遞歸工具類

遞歸和尾遞歸