兩個小例子輕松搞懂 java 中遞歸與尾遞歸的優(yōu)化操作

更新時間：2020年09月16日 08:38:14 作者：BigData_Hubert

這篇文章主要介紹了兩個小例子輕松搞懂 java 中遞歸與尾遞歸的優(yōu)化操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧

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

一、遞歸，偽遞歸，迭代實現(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基礎的 for 循環(huán)去實現(xiàn)。而在遞歸和尾遞歸實際上都是java 基礎 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)用同一個方法” 來進行優(yōu)化的。為了解決遞歸的開銷大問題，使用尾遞歸優(yōu)化，具體分兩種方法：

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

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

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

尾遞歸的形式：

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

遞歸的本質(zhì)是某個方法調(diào)用了自身，尾遞歸這種形式就要求：某個方法調(diào)用自身這件事，一定是該方法做的最后一件事（所以當有需要返回值的時候會是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)化

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

一方面是因為在遞歸調(diào)用自身的時候，這一層函數(shù)已經(jīng)沒有要做的事情了，雖然被遞歸調(diào)用的函數(shù)是在當前的函數(shù)里，但是他們之間的關(guān)系已經(jīng)在傳參的時候了斷了，也就是這一層函數(shù)的所有變量什么的都不會再被用到了，所以當前函數(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)用，那么該線程對應的棧就會增加一個存儲單元，即棧幀 (frame)。在frame 中，保存有該方法調(diào)用的參數(shù)、局部變量和返回地址。Java的參數(shù)和局部變量只能是基本類型的變量(比如 int)，或者對象的引用(reference) 。因此，在棧中，只保存有基本類型的變量和對象引用。而引用所指向的對象保存在堆中。具體如下圖所示：

當被調(diào)用方法運行結(jié)束時，該方法對應的幀將被刪除，參數(shù)和局部變量所占據(jù)的空間也隨之釋放。線程回到原方法，繼續(xù)執(zhí)行。當所有的棧都清空時，程序也隨之運行結(jié)束。如上所述，棧 (stack)可以自己照顧自己。但堆必須要小心對待。堆是 JVM中一塊可自由分配給對象的區(qū)域。當我們談論垃圾回收 (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)用自己的方法相當于在內(nèi)存中緩存一個Object 的camouflageFibonacci 方法對象的引用，不會去釋放，直到程序結(jié)束。