廢話不多說，我們直接上兩個最常見的小例子：

一、遞歸，偽遞歸，迭代實現n!

package com.njbdqn.test02;/** * 遞歸，偽遞歸，迭代實現n! */public class RecursionTest { public static void main(String[] args) { System.out.println(recurse(5)); //遞歸顯示 System.out.println(camouflageRecurse(5, 1)); //偽遞歸 System.out.println(iteration(5)); //迭代 } /** * n的階乘，尾遞歸實現方式 * * @param n * @param result 計算保存的中間結果 * @return 最終結果 */ public static int camouflageRecurse(int n, int result) { if (n == 1) { return result; } else { result = result * n; return camouflageRecurse(n - 1, result); } } /** * 求 n 的階乘遞歸調用方式 * * @param n n個數的階乘 * @return n個數階乘的結果 */ public static int recurse(int n) { if (n == 1) { return 1; } else { return n * recurse(n - 1); } } /** * 用迭代的方法實現n的階乘 * * @param n * @return */ public static int iteration(int n) { int result = 1; for (int i = 2; i <= n; ++i) { result *= i; } return result; }}

二、斐波那契數列的遞歸和迭代實現求和

package com.njbdqn.test02;/** * 斐波那契數列的遞歸和迭代實現求和 * 0 1 1 2 3 5 8 13 21 34 55 89 */public class FibonacciTest { public static void main(String[] args) { System.out.println(fibonacciRecurse(14)); System.out.println(fibonacciIteration(14)); System.out.println(camouflageFibonacci(14,1,0)); } /** * 遞歸調用實現斐波那契數列 * * @param n * @return */ public static int fibonacciRecurse(int n) { if (n == 1) { return 0; } else if (n == 2) { return 1; } else { return fibonacciRecurse(n - 1) + fibonacciRecurse(n - 2); } } /** * 迭代實現斐波那契數列 * 0 1 1 2 3 5 8 13 21 34 55 89 * * @param n * @return */ public static int fibonacciIteration(int n) { int fab = 0; //最終結果 n的值 int pre = 1; //記錄n-1值 int p = 0; //記錄n-2的位置 if (n == 1) { fab = 0; } else if (n == 2) { fab = 1; } for (int i = 2; i < n; ++i) { fab = pre + p; p = pre; pre = fab; } return fab; } /** * 斐波那契數列尾遞歸實現 * 0 1 1 2 3 5 8 13 21 34 55 89 * * @param n * @return */ public static int camouflageFibonacci(int n, int result1,int result2) { if (n == 0) { return result1; } else { return camouflageFibonacci(n - 1, result2,result1+result2) ; } }}

上述兩個小例子我們都采用了迭代、遞歸和尾遞歸的方法去實現。迭代不必說，就是用我們java基礎的 for 循環去實現。而在遞歸和尾遞歸實際上都是java 基礎 oop 的自己調用自己方法的實現。尾遞歸實際上是對遞歸的優化。

遞歸

遞歸的本質是，某個方法中調用了自身。本質還是調用一個方法，只是這個方法正好是自身而已。

如第二個例子斐波那契數列的遞歸return fibonacciRecurse(n - 1) + fibonacciRecurse(n - 2)部分執行示意圖如下所示：

遞歸的三大特性：

調用的是同一個方法

因為調用的是同一個方法，所以只需要寫一個方法，就可以讓你輕松調用無數次，所以調用的方法數可能非常巨大，其實在實際問題中往往都是方法數調用巨大的情況。

在自身中調用自身，本身就是嵌套調用（棧幀無法回收，開銷巨大）

遞歸的局限性：

因為遞歸調用的方法數大都非常巨大和嵌套調用帶來的棧幀無法回收，所以遞歸調用最大的詬病就是開銷巨大，棧幀和堆一起爆掉，俗稱內存溢出泄露。

java為了優化遞歸帶來的內存溢出泄露，就有了尾遞歸的誕生。那么尾遞歸是如何優化遞歸的呢？

尾遞歸

尾遞歸優化是利用上面的第一個特點 “調用同一個方法” 來進行優化的。為了解決遞歸的開銷大問題，使用尾遞歸優化，具體分兩種方法：

尾遞歸優化方式：

尾遞歸的形式：把遞歸調用的形式寫成尾遞歸的形式

編譯器對尾遞歸的優化：編譯器碰到尾遞歸，自動按照某種特定的方式進行優化編譯

尾遞歸的形式：

尾遞歸其實只是一種對遞歸的特殊寫法，這種寫法原本并不會帶來跟遞歸不一樣的影響，它只是寫法不一樣而已，寫成這樣不會有任何優化效果，該爆的棧和幀都還會爆

遞歸的本質是某個方法調用了自身，尾遞歸這種形式就要求：某個方法調用自身這件事，一定是該方法做的最后一件事（所以當有需要返回值的時候會是return f(n)，沒有返回的話就直接是f(n)了）

這個f(n)外不能加其他東西，因為這就不是最后一件事了，值返回來后還要再干點其他的活，變量空間還需要保留。比如如果有返回值的，你不能：乘個常數 return 3f(n)；乘個n return n*f(n)；甚至是 f(n)+f(n-1)…

另外，使用return的尾遞歸還跟函數式編程有一點關系

編譯器對尾遞歸的優化

簡單說就是重復利用同一個棧幀，不僅不用釋放上一個，連下一個新的都不用開，效率非常高

一方面是因為在遞歸調用自身的時候，這一層函數已經沒有要做的事情了，雖然被遞歸調用的函數是在當前的函數里，但是他們之間的關系已經在傳參的時候了斷了，也就是這一層函數的所有變量什么的都不會再被用到了，所以當前函數雖然沒有執行完，不能彈出棧，但它確實已經可以出棧了

另一方面是正因為調用的是自身，所以需要的存儲空間是一毛一樣的，那干脆重新刷新這些空間給下一層利用就好了，不用銷毀再另開空間

如第二個例子斐波那契數列的尾遞歸return camouflageFibonacci(n - 1, result2,result1+result2)部分執行示意圖如下所示：

說到這里你很容易聯想到JAVA中的自動垃圾回收機制，同是處理內存問題的機制，尾遞歸優化跟垃圾回收是不是有什么關系，這是不是就是JAVA不實現尾遞歸優化的原因？

垃圾回收（GC）與 尾遞歸

首先我們需要談一下內存機制，這里我們需要了解內存機制的兩個部分：棧和堆。

在Java中， JVM中的棧記錄了線程的方法調用。每個線程擁有一個棧。在某個線程的運行過程中， 如果有新的方法調用，那么該線程對應的棧就會增加一個存儲單元，即棧幀 (frame)。在frame 中，保存有該方法調用的參數、局部變量和返回地址。Java的參數和局部變量只能是 基本類型 的變量(比如 int)，或者對象的引用(reference) 。因此，在棧中，只保存有基本類型的變量和對象引用。而引用所指向的對象保存在堆中。具體如下圖所示：

當被調用方法運行結束時，該方法對應的幀將被刪除，參數和局部變量所占據的空間也隨之釋放。線程回到原方法，繼續執行。當所有的棧都清空時，程序也隨之運行結束。如上所述，棧 (stack)可以自己照顧自己。但堆必須要小心對待。堆是 JVM中一塊可自由分配給對象的區域。當我們談論垃圾回收 (garbage collection) 時，我們主要回收堆(heap)的空間。Java的普通對象存活在堆中。與棧不同，堆的空間不會隨著方法調用結束而清空（即使它在棧上的引用已經被清空了）（也不知道為什么不直接同步清空）。因此，在某個方法中創建的對象，可以在方法調用結束之后，繼續存在于堆中。這帶來的一個問題是，如果我們不斷的創建新的對象，內存空間將最終消耗殆盡。如果沒有垃圾回收機制的話，你就需要手動地顯式分配及釋放內存，如果你忘了去釋放內存，那么這塊內存就無法重用了（不管是什么局部變量還是其他的什么）。這塊內存被占有了卻沒被使用，這種場景被稱之為內存泄露。

如下圖所示：第二個例子斐波那契數列的尾遞歸每次調用自己的方法相當于在內存中緩存一個Object 的camouflageFibonacci 方法對象的引用，不會去釋放，直到程序結束。

最原始的情況，都是需要手動釋放堆中的對象，所以你經常需要考慮對象的生存周期，但是JAVA則引入了一個自動垃圾回收的機制，它能智能地釋放那些被判定已經沒有用的對象。

尾遞歸優化和垃圾回收最本質的區別是，尾遞歸優化解決的是內存溢出的問題，而垃圾回收解決的是內存泄露的問題。

內存泄露：指程序中動態分配內存給一些臨時對象，但是對象不會被GC所回收，它始終占用內存。即被分配的對象可達但已無用。

內存溢出：指程序運行過程中無法申請到足夠的內存而導致的一種錯誤。內存溢出通常發生于OLD段或Perm段垃圾回收后，仍然無內存空間容納新的Java對象的情況。

從定義上可以看出內存泄露是內存溢出的一種誘因，不是唯一因素。

自動垃圾回收機制的特點是：

解決了所有情況下的內存泄露的問題，但還可以由于其他原因內存溢出

針對內存中的堆空間

正在運行的方法中的堆中的對象是不會被管理的，因為還有引用（棧幀沒有被清空）

一般簡單的自動垃圾回收機制是采用 引用計數 (reference counting)的機制。每個對象包含一個計數器。當有新的指向該對象的引用時，計數器加 1。當引用移除時，計數器減 1，當計數器為0時，認為該對象可以進行垃圾回收

與之相對，尾遞歸優化的特點是：

優化了遞歸調用時的內存溢出問題

針對內存中的堆空間和棧空間

只在遞歸調用的時候使用，而且只能對于寫成尾遞歸形式的遞歸進行優化

正在運行的方法的堆和棧空間正是優化的目標

以上這篇兩個小例子輕松搞懂 java 中遞歸與尾遞歸的優化操作就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持好吧啦網。