遞迴 Recursion

在前一章中，我們介紹了函數的其他應用以及細節。在這一章中，我們要介紹更進階的應用：遞迴 Recursion！

遞迴這個觀念其實很簡單，但也是許多人的惡夢。尤其是初學程式的人，常常不知道如何除錯，或是邏輯轉不過來。

我一開始也是非常討厭遞迴，因為我不知道該如何用遞迴的方式寫程式碼，也是經過大量的練習，才慢慢地對遞迴這個觀念有些感覺。

但不用怕！在這一章中，我們會來認識遞迴，以及看看幾個簡單的例子！

什麼是遞迴

遞迴這個概念其實很簡單，就是當一個函數呼叫他自己的時候，我們就會說這是一個遞迴函數 Recursive Function。聽到這裡可能有人會問了，為什麼函數會需要呼叫他自己呢？

這就要來說到遞迴的本質了。遞迴的本質概念，其實是將原本的問題拆解成一個一個小問題，並分別去解決，最後才會解決原本的問題。還是聽不懂嗎？沒關係我們先知道這個概念，在接下來的例子中我們會來了解的！

簡單範例

這邊我們就來看一個超級簡單的範例，在這個範例中，我們要寫一個函數，這個函數會幫我們計算從數字 1 加到數字 x 的總和。

我們先來用前面學到的 for 迴圈來解決，這也是一般人會想到的解決辦法：

int sum(int x)
{
    int total = 0;
    for (int i = 1; i <= x; ++i)
    {
        total += i;
    }
    return total;
}

很簡單吧！

接下來讓我們用遞迴的方式來解決這個問題！還記得前面我們說過，遞迴的核心邏輯是將原本的問題拆解成一個一個小問題，最後在解決大問題嗎？

我們來思考一下，如果我們想要計算 1 到 10 的總和，那比這個問題再小一點的問題，是不是 1 到 9 的總和？

如果我們有 1 到 9 的總和，那 1 到 10 的總和是不是就是 10 +（1 到 9 的總和）？我們用這個概念先寫出一個遞迴的基本形狀：

int sum(int x)
{
    return x + sum(x - 1);
}

接下來，讓我們來思考一下，這個問題的「最小問題」是什麼。為什麼這很重要呢？因為我們總不能將原本的問題無止盡的拆分下去，我們必須要知道什麼時候可以停止拆分，並往回推算。

所以這個問題的最小問題，是不是就是當我們計算到數字 1 到 1 的總和就好了？因為我們沒有必要再去計算數字 1 到 0 的總和，這沒有意義了。所以代表當我們的變數 x 是 1 的時候，就可以停止並往回推送結果。

int sum(int x)
{
    if (x == 1)
        return 1;
    return x + sum(x - 1);
}

這就是我們最終的遞迴函數！我們可以看到相比於迭代，也就是 for 迴圈的形式，是不是簡潔不少？

為了更容易理解，我們來視覺化一下這個遞迴的過程

由上面的圖我們可以更清楚地知道，我們遇到了一個大問題（計算 sum(3)），為了解決他，我們將它拆解為小問題（計算 sum(2)），並試圖解決小問題。再接著拆解為更小的問題（計算 sum(1)）。

等到我們有了小問題的結果後，我們就可以將結果回傳給上一層大問題，最後解決我們原本的問題。希望這樣有幫助到你們理解！

遞迴 v.s. 迭代

由上面我們可以看到，同一個問題可以用遞迴的方式解，也可以用迭代的方式解。更進一步地說，其實科學家已經證明，每一個問題一定都有遞迴的解法也有迭代的解法，兩種解法是同時存在的。

那我們什麼時候應該用迭代，什麼時候應該用遞迴呢？他們之間又有什麼優缺點呢？

讓我們來看看這個表格：

所以我們可以知道遞迴和迭代解法各有優缺點。雖然說每個問題都有遞迴和迭代的解法，但有些問題使用遞迴的方式解反而會讓程式碼不容易理解，遇到問題的時候難以除錯等等，在這時候使用迭代反而是更好的選擇。但是以我們上面的簡單的例子，使用遞迴的解法就非常簡潔易懂！

想了解更多的話可以看看這篇 Stack Overflow 的討論！

經典範例

看完簡單的例子並有了初步理解後，讓我們來看看一個經典的遞迴範例：FIBONACCI 數列！

什麼是 Fibonacci 數列呢？在這個數列中，當前的數字會是前面兩個數字的和，除了一開始的 0 和 。所以，以下這個就是 Fibonacci 數列：

0 1 1 2 3 5 8 13 21 ...

這樣的問題，利用迭代 for 迴圈的方式非常好寫，但我們要怎麼利用遞迴 recursion 的方式解決這個問題呢？

首先，我們要記得一個遞迴的核心觀念：將原本的問題拆解為小問題，從小問題開始著手。

我們來看看，21 這個數字是怎麼來的？是不是前面兩個數字，也就是 8 和 13 的相加。那 13 呢？是不是也是他前面的兩個數字相加，也就是 5 和 8。

所以當我們想要求得第 n 個數會是多少時，我們只需要將在他前面的兩個數字相加就好，也就是 n – 1 和 n – 2。所以我們可以寫成下面這樣：

int sum(int n)
{
    return sum(n - 1) + sum(n - 2);
}

但還記得我們前面提到的終止條件嗎？也就是這個問題的最小問題是什麼？

是不是就是第一個跟第二個數！因為這兩個數是我們定義的，所以我們要將這兩個條件加進我們的程式碼，防止問題繼續被拆分下去。所以最終我們的程式碼就長這樣：

int sum(int n)
{
    if (n == 1)
    {
        return 0;
    }
    else if (n == 2)
    {
        return 1;
    }
    else
    {
        return sum(n - 1) + sum(n - 2);
    }
}

這一篇文章裡有很棒的圖片範例，讓我們可以更清楚在這個例子中，迴圈的呼叫流程，以及總共被呼叫了多少次等等。

總結

基本的遞迴觀念就介紹到這邊啦！在這篇文章中我們只介紹了非常非常基礎的遞迴觀念，包括什麼是遞迴，遞迴如何運作，遞迴和迭代的差別等等。

但要真的到熟悉遞迴，看到一個問題就知道該如何用遞迴去解，需要大量的練習，有時候甚至需要一點直覺。而且有些題目真的是非常難用遞迴想出來。

除此之外，遞迴還有更進階的應用：動態規劃 Dynamic Programming。主要功能是為了加速遞迴的運行速度，但這又是更難的觀念了！

如果想看或是親自練習更多遞迴的題目，這裡推薦一個不錯的網站：https://www.w3resource.com/cpp-exercises/recursion/index.php

希望大家有招一日都可以成為遞迴大師！