遞歸方法在C語言中的常見應用場景包括:
計算階乘(Factorial): 階乘是一個經典的遞歸應用場景。階乘函數可以用遞歸方式實現,如下所示:
#include<stdio.h>
int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int main() {
int n = 5;
printf("Factorial of %d = %d\n", n, factorial(n));
return 0;
}
計算斐波那契數列(Fibonacci sequence): 斐波那契數列是另一個常見的遞歸應用場景。斐波那契數列函數可以用遞歸方式實現,如下所示:
#include<stdio.h>
int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
int main() {
int n = 10;
printf("Fibonacci of %d = %d\n", n, fibonacci(n));
return 0;
}
二分查找(Binary Search): 二分查找是在有序數組中查找特定元素的算法。遞歸方法可以簡化二分查找的實現,如下所示:
#include<stdio.h>
int binary_search(int arr[], int left, int right, int target) {
if (right >= left) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] > target) {
return binary_search(arr, left, mid - 1, target);
}
return binary_search(arr, mid + 1, right, target);
}
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 10;
int result = binary_search(arr, 0, n - 1, target);
(result == -1) ? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
漢諾塔問題(Tower of Hanoi): 漢諾塔問題是一個經典的遞歸問題,可以用遞歸方法解決。以下是一個簡單的實現:
#include<stdio.h>
void tower_of_hanoi(int n, char from_rod, char to_rod, char aux_rod) {
if (n == 1) {
printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
return;
}
tower_of_hanoi(n - 1, from_rod, aux_rod, to_rod);
printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
tower_of_hanoi(n - 1, aux_rod, to_rod, from_rod);
}
int main() {
int n = 4;
tower_of_hanoi(n, 'A', 'C', 'B');
return 0;
}
這些場景展示了遞歸在C語言中的常見應用。然而,需要注意的是,遞歸可能會導致棧溢出和性能下降。在實際編程中,應根據問題的具體情況選擇合適的方法。