1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156
| #include <stdio.h> #include <string.h>
long long factorial(int n) { if (n <= 1) { return 1; } return n * factorial(n - 1); }
long long fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n - 1) + fibonacci(n - 2); }
long long fibonacci_memo(int n, long long memo[]) { if (n <= 1) { return n; } if (memo[n] != -1) { return memo[n]; } memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo); return memo[n]; }
void reverse_string(char str[], int start, int end) { if (start >= end) { return; } char temp = str[start]; str[start] = str[end]; str[end] = temp; reverse_string(str, start + 1, end - 1); }
int binary_search(int arr[], int left, int right, int target) { if (left > right) { return -1; } int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } if (arr[mid] > target) { return binary_search(arr, left, mid - 1, target); } else { return binary_search(arr, mid + 1, right, target); } }
void hanoi(int n, char from, char to, char aux) { if (n == 1) { printf("将盘子 1 从 %c 移动到 %c\n", from, to); return; } hanoi(n - 1, from, aux, to); printf("将盘子 %d 从 %c 移动到 %c\n", n, from, to); hanoi(n - 1, aux, to, from); }
int array_sum(int arr[], int size) { if (size <= 0) { return 0; } return arr[size - 1] + array_sum(arr, size - 1); }
int main(void) { printf("=== 递归编程演示 ===\n"); int n = 5; printf("阶乘计算:\n"); printf("%d! = %lld\n", n, factorial(n)); printf("\n斐波那契数列:\n"); printf("普通递归 fibonacci(%d) = %lld\n", 10, fibonacci(10)); long long memo[50]; for (int i = 0; i < 50; i++) { memo[i] = -1; } printf("记忆化递归 fibonacci(%d) = %lld\n", 40, fibonacci_memo(40, memo)); printf("\n字符串反转:\n"); char str[] = "Hello, World!"; printf("原字符串: %s\n", str); reverse_string(str, 0, strlen(str) - 1); printf("反转后: %s\n", str); printf("\n二分查找:\n"); int sorted_array[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; int array_size = sizeof(sorted_array) / sizeof(sorted_array[0]); int target = 7; int index = binary_search(sorted_array, 0, array_size - 1, target); if (index != -1) { printf("在索引 %d 处找到 %d\n", index, target); } else { printf("未找到 %d\n", target); } printf("\n汉诺塔问题 (3个盘子):\n"); hanoi(3, 'A', 'C', 'B'); printf("\n数组求和:\n"); int numbers[] = {1, 2, 3, 4, 5}; int sum = array_sum(numbers, 5); printf("数组 {1, 2, 3, 4, 5} 的和为: %d\n", sum); return 0; }
|