廢話不多說(shuō)，我們直接上兩個(gè)最常見(jiàn)的小例子：

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

package com.njbdqn.test02;

/**
 * 遞歸，偽遞歸，迭代實(shí)現(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的階乘，尾遞歸實(shí)現(xiàn)方式
  *
  * @param n
  * @param result 計(jì)算保存的中間結(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個(gè)數(shù)的階乘
  * @return n個(gè)數(shù)階乘的結(jié)果
  */
 public static int recurse(int n) {
  if (n == 1) {
   return 1;
  } else {
   return n * recurse(n - 1);
  }
 }

 /**
  * 用迭代的方法實(shí)現(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ù)列的遞歸和迭代實(shí)現(xiàn)求和

package com.njbdqn.test02;

/**
 * 斐波那契數(shù)列的遞歸和迭代實(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)用實(shí)現(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);
  }
 }
 /**
  * 迭代實(shí)現(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ù)列尾遞歸實(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) ;
  }
 }
}

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

遞歸

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

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

遞歸的三大特性：

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

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

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

遞歸的局限性：

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

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

尾遞歸

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

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

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

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

尾遞歸的形式：

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

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

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

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

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

簡(jiǎn)單說(shuō)就是重復(fù)利用同一個(gè)棧幀，不僅不用釋放上一個(gè)，連下一個(gè)新的都不用開(kāi)，效率非常高

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

另一方面是正因?yàn)檎{(diào)用的是自身，所以需要的存儲(chǔ)空間是一毛一樣的，那干脆重新刷新這些空間給下一層利用就好了，不用銷毀再另開(kāi)空間

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

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

垃圾回收（GC）與 尾遞歸

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

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

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

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

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

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

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

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

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

自動(dòng)垃圾回收機(jī)制的特點(diǎn)是：

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

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

正在運(yùn)行的方法中的堆中的對(duì)象是不會(huì)被管理的，因?yàn)檫€有引用（棧幀沒(méi)有被清空）

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

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

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

針對(duì)內(nèi)存中的堆空間和?？臻g

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

正在運(yùn)行的方法的堆和?？臻g正是優(yōu)化的目標(biāo)

以上這篇兩個(gè)小例子輕松搞懂 java 中遞歸與尾遞歸的優(yōu)化操作就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論