Java - 递归：初學者指南

嘿，未來的Java巫師們！今天，我們要深入探索神奇的递归世界。別擔心，如果這聽起來像是《哈利波特》中的一個咒語——在本教程結束時，你將能像專家一樣施展递歸咒語！

Java - Recursion

什麼是递归？

想象一下，你在亂糟糟的房間裡找你丟失的襪子。你打開一個抽屜，裡面有另一個更小的抽屜。你打開那個，驚喜！裡面還有個更小的抽屜。這種打開抽屜中的抽屜的過程非常像編程中的递归。

在Java中，递归是一個方法為了解決問題而調用自己。這就像方法在說：“我知道部分答案，但剩下的，我會再問我自己一樣！”

递归在Java中是如何工作的？

讓我們一步一步來分解：

一個方法調用自己
有個條件可以停止递归（基礎情況）
問題被分解成更小、類似的子問題

以下是一個簡單的例子：

public class RecursiveCountdown {
public static void countdown(int n) {
if (n == 0) {
System.out.println("發射！");
} else {
System.out.println(n);
countdown(n - 1);
}
}

public static void main(String[] args) {
countdown(5);
}
}

在這個例子中，countdown是我們的递歸方法。它不斷地用一個更小的數字調用自己，直到達到零。讓我們看看發生了什麼：

countdown(5)打印5，然後調用countdown(4)
countdown(4)打印4，然後調用countdown(3)
這繼續直到...
countdown(0)打印“發射！”並停止

魔法發生的原因是，每個對countdown的調用都在等待下一個調用完成後才完成。這就像一疊薄餅——我們不停地添加（調用），直到我們完成，然後我們從頂部開始吃（返回）。

Java递歸示例

讓我們再看一些例子，真正了解递歸有多麼強大。

示例1：階乘計算

一個數字的階乘是該數字以下所有正整數的乘積。例如，5!（5的階乘）是5 4 3 2 1 = 120。

public class Factorial {
public static int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}

public static void main(String[] args) {
System.out.println("5的階乘是：" + factorial(5));
}
}

這是它的工作原理：

factorial(5)返回5 * factorial(4)
factorial(4)返回4 * factorial(3)
這繼續直到我們達到factorial(1)，它返回1
然後我們乘回去：1 2 3 4 5 = 120

示例2：斐波那契序列

斐波那契序列是一個數列，其中每個數字是前兩個數字的和。它從0和1開始，然後是1, 2, 3, 5, 8, 13，以此類推。

public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}

public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.print(fibonacci(i) + " ");
}
}
}

這個有點複雜：

對於fibonacci(5)，我們計算fibonacci(4) + fibonacci(3)
每個調用都會產生兩個更多的調用，以此類推
它形成了一棵調用樹，一直到底部的fibonacci(0)和fibonacci(1)
然後在返回的路上將所有結果加起來

在Java中使用递歸的優點

簡潔性：對於某些問題，递歸解決方案可能更容易理解。
代碼大小減少：递歸代碼可能更簡潔。
解決複雜問題：有些問題，如遍歷樹，自然適合用递歸。

在Java中使用递歸的缺點

內存使用：每個递歸調用都會增加調用堆棧，這可能會導致深度遞歸的堆棧溢出。
性能：由於多個函數調用的開銷，递歸解決方案可能會變慢。
調試困難：跟蹤遞歸調用可能具有挑戰性。

何時使用递歸

當處理可以分解成類似子問題的問題時，递歸表現出色。它非常適合：

樹的遍歷
圖算法
分而治之算法
回溯問題

递歸與迭代

有時，你可以使用遞歸或迭代（循環）解決問題。以下是一個快速比較：

方面	递归	迭代
代碼簡潔性	往往對複雜問題更簡單	對簡單任務更簡單
性能	可能因為函數調用開銷而變慢	通常更快
內存使用	可能使用更多內存（調用堆棧）	使用較少內存
問題適用性	對於具有遞歸性質的問題更好	對於簡單重複性任務更好

寫遞歸函數的技巧

始終有個基礎情況：這是你的退出條件。沒有它，你會永遠遞歸！
確保朝向基礎情況的進步：每個遞歸調用都應該使你更接近基礎情況。
相信遞歸：不要試圖在頭腦中追溯所有調用。相信你的函數對較小的輸入會工作。

結論

遞歸就像是編程中的一種超能力。它可能需要一些練習才能掌握，但一旦你做到了，你將會以全新的視角看待問題。記住，每當你使用遞歸時，你基本上是在代碼中創建了一個小時間機器，向過去和未來版本的你的函數發送信息。這有多酷？

繼續練習，你將能夠輕鬆解決複雜問題！如果你遇到無窮遞歸，記得用ctrl+C退出——不需要時間機器！開心編程，未來的遞歸大師們！

Credits: Image by storyset