Recursive problem

Recursive problem

Slience_Displace Lv2
  2024-10-23 2024-10-23 00 Created   2024-10-26 00:08:03 2024-10-26 00:08 Updated    
  • C 
 2.5k Words  12 Mins  

啊吧 啊吧 啊吧

Recursive Problem Summary

递归问题

1. 斐波那契数列

斐波那契数列的定义是：

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) （n >= 2）

C语言代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>

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

int main() {
    int n = 10;
    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));
    return 0;
}

2. 阶乘计算

阶乘的定义为：

  • n! = n * (n-1) * (n-2) * … * 1
  • 0! = 1

C语言代码：

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>

int factorial(int n) {
    if (n == 0) return 1;  // 0! = 1
    return n * factorial(n - 1);
}

int main() {
    int n = 5;
    printf("%d! = %d\n", n, factorial(n));
    return 0;
}

3. 汉诺塔问题

汉诺塔问题是经典的递归问题，目标是将所有盘子从源柱子移动到目标柱子，遵循以下规则：

  • 每次只能移动一个盘子。
  • 不能将较大的盘子放在较小的盘子上。

C语言代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, aux, to); // 递归移动n-1个盘子到辅助柱
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, to, from); // 递归将n-1个盘子从辅助柱移动到目标柱
}

int main() {
    int n = 3; // 盘子的数量
    hanoi(n, 'A', 'C', 'B'); // A为源柱，B为辅助柱，C为目标柱
    return 0;
}

4. 二分查找

二分查找是递归的典型应用，前提是数组已经排序。它通过每次将数组的查找范围减半来寻找目标值。

C语言代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>

int binary_search(int arr[], int low, int high, int target) {
    if (low > high) return -1; // 未找到
    int mid = (low + high) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target) return binary_search(arr, low, mid - 1, target);
    return binary_search(arr, mid + 1, high, target);
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    int result = binary_search(arr, 0, n - 1, target);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");
    return 0;
}

5. 字符串逆序

使用递归将字符串逆序输出。

C语言代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>

void reverse_string(char *str) {
    if (*str == '\0') return; // 基本情况：字符串结尾
    reverse_string(str + 1);   // 递归调用
    putchar(*str);             // 输出当前字符
}

int main() {
    char str[] = "hello";
    reverse_string(str);
    printf("\n");
    return 0;
}

6. 最大公约数（欧几里得算法）

通过递归方法计算两个数的最大公约数。公式为：GCD(a, b) = GCD(b, a % b)，其中a % b是a除以b的余数。

C语言代码：

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) return a;  // 递归终止条件
    return gcd(b, a % b);  // 递归调用
}

int main() {
    int a = 56, b = 98;
    printf("GCD of %d and %d is %d\n", a, b, gcd(a, b));
    return 0;
}

7. 全排列

给定一个数组，使用递归方法生成该数组的所有排列组合。

C语言代码：

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
#include <stdio.h>

void swap(char *x, char *y) {
    char temp = *x;
    *x = *y;
    *y = temp;
}

void permute(char *str, int l, int r) {
    if (l == r)
        printf("%s\n", str);
    else {
        for (int i = l; i <= r; i++) {
            swap((str + l), (str + i));
            permute(str, l + 1, r);
            swap((str + l), (str + i)); // 回溯
        }
    }
}

int main() {
    char str[] = "ABC";
    int n = strlen(str);
    permute(str, 0, n - 1);
    return 0;
}

好的，再列举一些经典的递归问题，并用C语言解决。

8. 八皇后问题

八皇后问题是经典的递归与回溯算法问题，要求在8x8的棋盘上放置8个皇后，使得它们彼此不能攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。

C语言代码：

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
#include <stdio.h>
#define N 8

int board[N][N]; // 棋盘

// 检查某个位置是否安全
int is_safe(int row, int col) {
    for (int i = 0; i < col; i++)
        if (board[row][i]) return 0;

    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j]) return 0;

    for (int i = row, j = col; i < N && j >= 0; i++, j--)
        if (board[i][j]) return 0;

    return 1;
}

// 递归函数解决八皇后问题
int solve_nqueens(int col) {
    if (col >= N) return 1; // 成功放置所有皇后

    for (int i = 0; i < N; i++) {
        if (is_safe(i, col)) {
            board[i][col] = 1;

            if (solve_nqueens(col + 1)) return 1;

            board[i][col] = 0; // 回溯
        }
    }
    return 0;
}

// 打印棋盘
void print_board() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf("%d ", board[i][j]);
        printf("\n");
    }
}

int main() {
    if (solve_nqueens(0)) {
        print_board();
    } else {
        printf("Solution does not exist\n");
    }
    return 0;
}

9. 汉诺塔问题

汉诺塔问题是经典的递归问题，要求将所有盘子从源柱移动到目标柱，同时满足不能将较大的盘子放在较小的盘子上。

C语言代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>

void hanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from_rod, to_rod);
        return;
    }
    hanoi(n - 1, from_rod, aux_rod, to_rod);
    printf("Move disk %d from %c to %c\n", n, from_rod, to_rod);
    hanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main() {
    int n = 3; // 盘子的数量
    hanoi(n, 'A', 'C', 'B'); // A是源柱, C是目标柱, B是辅助柱
    return 0;
}

10. 最大子数组和

给定一个整数数组，找到具有最大和的连续子数组，并返回其和。这个问题也可以使用递归来解决。

C语言代码：

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
#include <stdio.h>

// 递归计算最大子数组和
int max_cross_sum(int arr[], int l, int m, int h) {
    int sum = 0, left_sum = -2147483648;
    for (int i = m; i >= l; i--) {
        sum += arr[i];
        if (sum > left_sum) left_sum = sum;
    }

    sum = 0, right_sum = -2147483648;
    for (int i = m + 1; i <= h; i++) {
        sum += arr[i];
        if (sum > right_sum) right_sum = sum;
    }

    return left_sum + right_sum;
}

int max_subarray_sum(int arr[], int l, int h) {
    if (l == h) return arr[l];

    int m = (l + h) / 2;
    return fmax(fmax(max_subarray_sum(arr, l, m), max_subarray_sum(arr, m + 1, h)), max_cross_sum(arr, l, m, h));
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_sum = max_subarray_sum(arr, 0, n - 1);
    printf("Maximum subarray sum is %d\n", max_sum);
    return 0;
}

11. 全组合问题

给定一个数组，输出该数组的所有可能的子集（组合），这是一个经典的递归与回溯问题。

C语言代码：

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
#include <stdio.h>

void combine(int arr[], int data[], int start, int end, int index, int r) {
    if (index == r) {
        for (int j = 0; j < r; j++) {
            printf("%d ", data[j]);
        }
        printf("\n");
        return;
    }

    for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
        data[index] = arr[i];
        combine(arr, data, i + 1, end, index + 1, r);
    }
}

int main() {
    int arr[] = {1, 2, 3, 4};
    int r = 2; // 组合的大小
    int data[r];
    int n = sizeof(arr) / sizeof(arr[0]);
    combine(arr, data, 0, n - 1, 0, r);
    return 0;
}

12. 递归实现二叉树的前序遍历

前序遍历是指按照“根节点 -> 左子树 -> 右子树”的顺序遍历二叉树。

C语言代码：

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
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* new_node(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void pre_order(struct Node* node) {
    if (node == NULL) return;

    printf("%d ", node->data); // 打印根节点
    pre_order(node->left);     // 递归遍历左子树
    pre_order(node->right);    // 递归遍历右子树
}

int main() {
    struct Node* root = new_node(1);
    root->left = new_node(2);
    root->right = new_node(3);
    root->left->left = new_node(4);
    root->left->right = new_node(5);

    printf("Preorder traversal: ");
    pre_order(root);
    printf("\n");

    return 0;
}

13. 数塔问题（递归 + 动态规划）

在一个数塔中，每层有若干个数字，从顶端开始走，每次只能走到下一层的左或右相邻的节点，求走到塔底的路径和最大值。

C语言代码：

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
#include <stdio.h>
#define MAX 100

int tower[MAX][MAX];
int dp[MAX][MAX];
int n; // 层数

int max_sum(int i, int j) {
    if (i == n - 1) return tower[i][j]; // 到达底层
    if (dp[i][j] != -1) return dp[i][j]; // 记忆化搜索
    dp[i][j] = tower[i][j] + fmax(max_sum(i + 1, j), max_sum(i + 1, j + 1));
    return dp[i][j];
}

int main() {
    printf("Enter the number of levels: ");
    scanf("%d", &n);
    printf("Enter the tower values:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            scanf("%d", &tower[i][j]);
            dp[i][j] = -1; // 初始化dp数组
        }
    }
    printf("Maximum sum = %d\n", max_sum(0, 0));
    return 0;
}

14. 二分查找

在有序数组中查找某个元素的位置。二分查找可以用递归来实现。

C语言代码：

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
cCopy code#include <stdio.h>

int binary_search(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 binary_search(arr, l, mid - 1, x);
        return binary_search(arr, mid + 1, r, x);
    }
    return -1; // 如果找不到
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binary_search(arr, 0, n - 1, x);
    if (result == -1)
        printf("Element not found\n");
    else
        printf("Element is present at index %d\n", result);
    return 0;
}

15. 正则匹配问题

递归实现一个简单的正则匹配算法，判断字符串是否匹配给定的模式，模式中允许包含 .（表示任意字符）和 *（表示任意个字符）。

C语言代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
cCopy code#include <stdio.h>

int is_match(const char* text, const char* pattern) {
    if (*pattern == '\0') return *text == '\0';
    int first_match = (*text != '\0' && (*text == *pattern || *pattern == '.'));
    
    if (*(pattern + 1) == '*') {
        return (is_match(text, pattern + 2) || (first_match && is_match(text + 1, pattern)));
    } else {
        return first_match && is_match(text + 1, pattern + 1);
    }
}

int main() {
    char text[] = "aab";
    char pattern[] = "c*a*b";
    if (is_match(text, pattern)) {
        printf("Pattern matches the text\n");
    } else {
        printf("Pattern does not match the text\n");
    }
    return 0;
}
  • Title: Recursive problem
  • Author: Slience_Displace
  • Created at: 2024-10-23 00:00:00
  • Updated at: 2024-10-26 00:08:03
  • Link: https://mikumikudaifans.github.io/Displace.github.io/2024/10/23/Recursive problem_List/
  • License: This work is licensed under CC BY-NC-SA 4.0.
 Comments
On this page
Recursive problem
  1. Recursive Problem Summary
    1. 1. 斐波那契数列
    2. 2. 阶乘计算
    3. 3. 汉诺塔问题
    4. 4. 二分查找
    5. 5. 字符串逆序
    6. 6. 最大公约数（欧几里得算法）
    7. 7. 全排列
    8. 8. 八皇后问题
    9. 9. 汉诺塔问题
    10. 10. 最大子数组和
    11. 11. 全组合问题
    12. 12. 递归实现二叉树的前序遍历
    13. 13. 数塔问题（递归 + 动态规划）
    14. 14. 二分查找
    15. 15. 正则匹配问题