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

一、遞歸，偽遞歸，迭代實現(xiàn)n!

package com.njbdqn.test02;/** * 遞歸，偽遞歸，迭代實現(xiàn)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的階乘，尾遞歸實現(xiàn)方式 * * @param n * @param result 計算保存的中間結(jié)果 * @return 最終結(jié)果 */ public static int camouflageRecurse(int n, int result) { if (n == 1) { return result; } else { result = result * n; return camouflageRecurse(n - 1, result); } } /** * 求 n 的階乘遞歸調(diào)用方式 * * @param n n個數(shù)的階乘 * @return n個數(shù)階乘的結(jié)果 */ public static int recurse(int n) { if (n == 1) { return 1; } else { return n * recurse(n - 1); } } /** * 用迭代的方法實現(xiàn)n的階乘 * * @param n * @return */ public static int iteration(int n) { int result = 1; for (int i = 2; i <= n; ++i) { result *= i; } return result; }}

二、斐波那契數(shù)列的遞歸和迭代實現(xiàn)求和

package com.njbdqn.test02;/** * 斐波那契數(shù)列的遞歸和迭代實現(xiàn)求和 * 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)); } /** * 遞歸調(diào)用實現(xiàn)斐波那契數(shù)列 * * @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); } } /** * 迭代實現(xiàn)斐波那契數(shù)列 * 0 1 1 2 3 5 8 13 21 34 55 89 * * @param n * @return */ public static int fibonacciIteration(int n) { int fab = 0; //最終結(jié)果 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; } /** * 斐波那契數(shù)列尾遞歸實現(xiàn) * 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) ; } }}

上述兩個小例子我們都采用了迭代、遞歸和尾遞歸的方法去實現(xiàn)。迭代不必說，就是用我們java基礎(chǔ)的 for 循環(huán)去實現(xiàn)。而在遞歸和尾遞歸實際上都是java 基礎(chǔ) oop 的自己調(diào)用自己方法的實現(xiàn)。尾遞歸實際上是對遞歸的優(yōu)化。

遞歸

遞歸的本質(zhì)是，某個方法中調(diào)用了自身。本質(zhì)還是調(diào)用一個方法，只是這個方法正好是自身而已。

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

遞歸的三大特性：

調(diào)用的是同一個方法

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

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

遞歸的局限性：

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

java為了優(yōu)化遞歸帶來的內(nèi)存溢出泄露，就有了尾遞歸的誕生。那么尾遞歸是如何優(yōu)化遞歸的呢？

尾遞歸

尾遞歸優(yōu)化是利用上面的第一個特點 “調(diào)用同一個方法” 來進(jìn)行優(yōu)化的。為了解決遞歸的開銷大問題，使用尾遞歸優(yōu)化，具體分兩種方法：

尾遞歸優(yōu)化方式：

尾遞歸的形式：把遞歸調(diào)用的形式寫成尾遞歸的形式

編譯器對尾遞歸的優(yōu)化：編譯器碰到尾遞歸，自動按照某種特定的方式進(jìn)行優(yōu)化編譯

尾遞歸的形式：

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

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

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

另外，使用return的尾遞歸還跟函數(shù)式編程有一點關(guān)系

編譯器對尾遞歸的優(yōu)化

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

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

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

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

說到這里你很容易聯(lián)想到JAVA中的自動垃圾回收機制，同是處理內(nèi)存問題的機制，尾遞歸優(yōu)化跟垃圾回收是不是有什么關(guān)系，這是不是就是JAVA不實現(xiàn)尾遞歸優(yōu)化的原因？

垃圾回收（GC）與 尾遞歸

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

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

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

如下圖所示：第二個例子斐波那契數(shù)列的尾遞歸每次調(diào)用自己的方法相當(dāng)于在內(nèi)存中緩存一個Object 的camouflageFibonacci 方法對象的引用，不會去釋放，直到程序結(jié)束。

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

尾遞歸優(yōu)化和垃圾回收最本質(zhì)的區(qū)別是，尾遞歸優(yōu)化解決的是內(nèi)存溢出的問題，而垃圾回收解決的是內(nèi)存泄露的問題。

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

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

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

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

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

針對內(nèi)存中的堆空間

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

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

與之相對，尾遞歸優(yōu)化的特點是：

優(yōu)化了遞歸調(diào)用時的內(nèi)存溢出問題

針對內(nèi)存中的堆空間和棧空間

只在遞歸調(diào)用的時候使用，而且只能對于寫成尾遞歸形式的遞歸進(jìn)行優(yōu)化

正在運行的方法的堆和棧空間正是優(yōu)化的目標(biāo)

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