题目（C语言递归）：在n枚硬币中，有一枚是假币（位置随机），并且已知假币比真币轻。通过一架天平来任意比较两组硬币，设计一个高效的算法来检测出这枚假币。 1、分别用二分法和三分法求解该问题（写在一起）。 2、输入：n（硬币数量)

在C语言中，使用递归策略结合二分法或三分法来解决这个问题可以提高查找效率。以下是两种方法的基本思路：

1. **二分法**（Halving Method, 适用于偶数硬币数量 n）：
- 当硬币数量 n 为 2 的倍数时，将硬币分成两半，每边放 n/2 枚硬币。
- 把天平两端各放一半，如果平衡，则假币在未称的那一半里；如果不平衡，假币在较轻的一端。
- 对剩下的一半再次应用此过程，直到找到假币。

2. **三分法**（Thirding Method, 适用于奇数硬币数量 n）：
- 将硬币分为三份，大约 n/3 枚一组，留一份备用。
- 分别称量两组，如果平衡，假币在未称的那组中；若不平衡，假币在较轻的一组。
- 将确定有假币的那组再平均分成三份，找出较轻的那一部分（大约 n/9 枚），然后继续这个过程，每次缩小搜索范围。
- 这样不断三分，最终会定位到假币。

对于输入的 `n` (硬币数量)，你可以编写一个递归函数，接受 n 作为参数，并根据 n 的奇偶性来决定执行二分法还是三分法。递归终止条件通常是当只剩下一枚硬币时，直接判断其重量即可。

**递归伪代码示例：**

void detectFakeCoin(int coins, int* weights, bool* fakeInLeft) {
    if (coins == 1) { // 基线条件：单个硬币，直接返回
        if (weights[0] < weights[1]) {
            *fakeInLeft = true;
        } else {
            *fakeInLeft = false;
        }
        return;
    }

    // 根据n的奇偶性选择二分法或三分法
    if (coins % 3 == 0 || coins == 1) { // 二分法处理偶数和单个硬币
        //...
    } else { // 三分法处理奇数
        //...
    }
}

int main() {
    int n;
    // 输入n
    int coins[] = {...}; // 硬币重量数组
    bool fakeInLeft; // 假币在哪一边标记

    detectFakeCoin(n, coins, &fakeInLeft);
    // 返回结果并处理假币信息
}