使用c语言递归：实现整数划分问题和汉诺塔问题，两个问题分开解决

在C语言中，递归是一种强大的工具，常用于解决需要将大问题分解成更小部分的问题。下面是递归实现整数划分问题（也称为“背包问题”简化版）和汉诺塔问题的例子：

### 整数划分问题（例如0/1背包问题）
这是一个动态规划问题，但也可以通过递归来理解。假设我们有一个整数n和一些物品，每个物品有自己的价值v[i]和重量w[i]。目标是找出一种分配方案，使得物品总重量不超过n的同时，总价值最大。

#include <stdio.h>

// 递归函数，返回给定重量范围内的最大价值
int knapSack(int capacity, int weight[], int val[], int n) {
    if (n == 0 || capacity == 0)
        return 0; // 如果剩余物品或容量为0，价值为0

    if (weight[n - 1] > capacity) // 当前物品超重，选择不放入
        return knapSack(capacity, weight, val, n - 1);
    
    // 两种情况：选或不选当前物品
    int include = val[n - 1] + knapSack(capacity - weight[n - 1], weight, val, n - 1); // 包含该物品
    int exclude = knapSack(capacity, weight, val, n - 1); // 不包含该物品

    return max(include, exclude); // 返回两者中的较大值作为结果
}

int main() {
    int capacity = 50;
    int weights[] = {10, 20, 30};
    int values[] = {60, 100, 120};
    int n = sizeof(weights) / sizeof(weights[0]);

    printf("最大价值: %d\n", knapSack(capacity, weights, values, n));
    return 0;
}

**注意:** 上述代码使用了`max()`函数，实际C语言中需自定义或引入库来获取最大值。

### 汉诺塔问题
汉诺塔是一个经典的递归问题，涉及三个柱子A、B和C以及一堆圆盘，规则是从A移动到C，只能将较小的圆盘放在较大的上面。以下是递归解决方案：

void 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;
    }
    
    // 将n-1个盘子从起始杆移到辅助杆
    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);

    // 最后的n-1个盘子从辅助杆移到终点杆
    hanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main() {
    int num_disks = 3;
    hanoi(num_disks, 'A', 'C', 'B');
    return 0;
}

这两个例子都展示了如何利用递归解决特定问题。递归通常会提供简洁的代码结构，但也需要注意防止无限循环，并确保有明确的递归终止条件。