C語言中的遞歸

你好，未來的程序员們！今天，我們將要深入探討編程中最引人入勝的概念之一：遞歸。別擔心，如果這聽起來讓人覺得害怕 - 到了這個教程的結尾，你將會成為遞歸的專家！讓我們一起踏上這個令人興奮的旅程。

C - Recursion

C語言中的遞歸函數是什麼？

想像你正在看著鏡子裡的自己，而你的背後還有另一面鏡子。你看到了無數個自己的倒影。這在編程中多少有點像遞歸！

遞歸函數是一個在其執行過程中調用自己的函數。就像一個函數說："嘿，我需要幫助。有誰比我更適合幫助我呢？...我自己！"

這裡有一個簡單的例子：

void countdown(int n) {
if (n == 0) {
printf("Blastoff!\n");
} else {
printf("%d\n", n);
countdown(n - 1);
}
}

在這個函數中，countdown 每次都會用一個較小的數字調用自己。這就像火箭倒數計時，我們不斷計數直到達到零，然後發射！

C語言中為什麼使用遞歸？

你可能會想："我們有循環，為什麼還要麻煩使用遞歸呢？" 好問題！遞歸有幾個優點：

它可以使某些問題的代碼更易於閱讀和更優雅。
它對於具有遞歸性質的任務非常適合，比如遍歷樹狀結構。
它可以減少複雜循環結構和臨時變量的需求。

然而，遞歸並不是每次都是最佳選擇。它可能會對某些問題來說記憶體使用密集且速度較慢。就像編程中的許多事情一樣，這是關於選擇正確的工具來完成工作。

使用遞歸計算階乘

讓我們來看一個遞歸的經典例子：計算階乘。數字 n 的階乘（寫作 n!）是所有小於或等於 n 的正整數的乘積。

這是我們如何遞歸地計算階乘：

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

讓我們來分解這個過程：

如果 n 等於 0 或 1，我們返回 1（這是我們的基本情況）。
否則，我們將 n 乘以 (n-1) 的階乘。

所以，如果我們調用 factorial(5)，這就是發生的事情：

5 * factorial(4)
5 (4 factorial(3))
5 (4 (3 * factorial(2)))
5 (4 (3 (2 factorial(1))))
5 (4 (3 (2 1)))
5 (4 (3 * 2))
5 (4 6)
5 * 24
120

這樣我們就得到了 - 5! = 120。

使用遞歸進行二分查找

二分查找是一種在排序列表中查找元素的效率高的算法。它通過不斷將搜索區間折半來工作。讓我們遞歸地實現它：

int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;

if (arr[mid] == x)
return mid;

if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);
}

return -1;
}

這個函數做以下事情：

計算中間索引。
如果中間元素是目標，我們就完成了！
如果目標小於中間元素，搜索左半部分。
如果目標大於中間元素，搜索右半部分。
如果我們找不到元素，返回 -1。

這就像一場高科技的"猜數字"遊戲，你總是猜剩餘範圍中的中間數字！

使用遞歸生成斐波那契數列

斐波那契序列是一個數列，其中每個數字都是前兩個數字的和。這是遞歸的完美候選者！

這是我們如何遞歸地生成斐波那契數字：

int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}

這個函數的工作原理如下：

如果 n 等於 0 或 1，我們返回 n（這是我們的基本情況）。
對於任何其他 n，我們返回前兩個斐波那契數字的和。

所以，如果我們調用 fibonacci(5)，這就是發生的事情：

fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(2) = fibonacci(1) + fibonacci(0)
fibonacci(1) = 1
fibonacci(0) = 0

反向工作，我們得到：

fibonacci(2) = 1 + 0 = 1
fibonacci(3) = 1 + 1 = 2
fibonacci(4) = 2 + 1 = 3
fibonacci(5) = 3 + 2 = 5

所以第五個斐波那契數字是 5！

常見的遞歸方法

這裡是我們討論過的常見遞歸方法的表格：

方法	描述	基本情況	遞歸情況
階乘	計算 n!	n = 0 或 1	n * factorial(n-1)
二分查找	在排序列表中查找元素	元素找到或不在數組中	搜索左或右半部分
斐波那契	生成斐波那契數字	n <= 1	fibonacci(n-1) + fibonacci(n-2)

記住，理解遞歸的關鍵是相信遞歸調用將正確地完成其工作。這就像將任務委託給自己的複製一樣 - 你知道他們會像你一樣處理它！

遞歸可能最初會讓人覺得有些難以理解，但隨著練習，它會成為你編程工具箱中的強大工具。繼續實驗，很快你將會到處看到遞歸解決方案！

開心地編程，並記住 - 要理解遞歸，你必須首先理解遞歸。 ?

Credits: Image by storyset