正确看待遞歸函數

什麼是遞歸函數

我們都知道基本上的程式設計語言都支援在一個函數中調用其他的函數。如果這個函數在内部調用它自己，那麼我們就稱這個函數為遞歸函數。

遞歸函數的作用

• 可以執行for或while語句相同的任務

• 有些情況可以少寫代碼，讓代碼看起來更簡練

  舉一個例子，數學中我們有學習過求一個正整數的階乘。階乘是基斯頓·卡曼（Christian Kramp，1760～1826）于 1808 年發明的運算符号，是數學術語。一個正整數的階乘（factorial）是所有小于及等于該數的正整數的積。我們使用PHP語言用兩種方法實作階乘的運算，代碼如下：

<?php
​
//使用遞歸的方式
function factorial_1($n){
  return $n == 1 ? 1 : $n * factorial($n - 1);
}
//使用while的方式
function factorial_2($n){
  $res = 1;
  while ($n > 1) {
    $res = $res * $n--;
  }
  return $res;
}
$n = 5;
echo "使用階乘的方式：" . factorial_1($n) . "<br>";
echo "使用while的方式： " . factorial_2($n) . "<br>";           

打開浏覽器運作該腳本，可以得到相同的結果。觀察兩個函數的實作，不難發現使用階乘的方式，代碼量看起來似乎是少一些，但是也沒有特别明顯。

遞歸函數的弊端

• 性能低于for和while,同時會占用更高的記憶體
• 如果不設定遞歸的邊界，那麼就會造成死循環，直接将伺服器跑崩
• 雖然可以替代for和while的實作，但是有些情況使用遞歸會顯得很難了解。這邊舉個例子（當時也是困擾苟哥我許久啊），代碼實作如下：

<?php
//用兩個方法實作将一個字元串逆置
​
//遞歸實作
function reverse_r($str) { 
  if (strlen($str)>0) {
    reverse_r(substr($str, 1)); 
  }
  echo substr($str, 0, 1);
  return; 
}
​
//for循環實作
function reverse_i($str) {
  for ($i=1; $i<=strlen($str); $i++) {
    echo substr($str, -$i, 1); 
  }
  return; 
}
​
reverse_r('Hello'); 
echo '<br />'; 
reverse_i('Hello');           

雖然兩個方法得到的結果是一樣的，但是明顯reverse_i這個方式是更好了解的，直接從字元串的最後一個位置開始逐個列印字元。而分析reverse_r這個方法，你會發現不是很好了解，如果你之前不知道一個事實——“函數内，當遇到子函數後并不是停止運作函數後面的代碼，而是儲存現場，去執行子函數，執行完恢複現場接着執行”，那麼我猜你一定很難了解程式是怎麼實作字元串逆置的。什麼意思呢？就是reverse_i腳本的第9行那句代碼會執行n次（n表示遞歸次數），但是每次執行的順序剛好是和函數的循環順序相反的，我們借助下圖來了解reverse_i是如何被執行的：

上圖中，右側帶數字的向下箭頭表示程式實際運作的代碼順序。被不同顔色的線連接配接的表示一個完整的函數體（因為我們剛剛說了遇到子函數後并不是停止運作函數後面的代碼，而是儲存現場，去執行子函數，執行完恢複現場接着執行），是以reverse_r('hello')雖然是最先被執行的，但是它的後一句代碼echo substr('hello', 0, 1) 卻是最後才被執行的。最後得到的列印效果也就實作了将字元串逆置，但是用遞歸這個方式确實不容易被了解啊。

應該使用遞歸函數嗎

從知識點全面性的角度，我覺得可以也應該去學習遞歸思想。但是在實際編碼過程中，我覺得盡量少用，而是使用for或while去替代它，這樣會讓你少走很多彎路。