/*
 * 示例19：递归（Recursion）
 * 功能：学习递归的概念，函数调用自身
 * 递归必须有终止条件，否则会无限循环
 */

#include <stdio.h>

// 递归计算阶乘：n! = n * (n-1) * ... * 1
// 例如：5! = 5 * 4 * 3 * 2 * 1 = 120
int factorial(int n) {
    // 终止条件：当 n 为 0 或 1 时，返回 1
    if (n <= 1) {
        return 1;
    }
    // 递归调用：n! = n * (n-1)!
    return n * factorial(n - 1);
}

// 递归计算斐波那契数列
// 斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21...
// 每个数是前两个数之和
int fibonacci(int n) {
    // 终止条件
    if (n <= 2) {
        return 1;
    }
    // 递归调用
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// 递归计算 1 到 n 的和
int sumToN(int n) {
    if (n <= 1) {
        return 1;
    }
    return n + sumToN(n - 1);
}

int main() {
    // 计算 5 的阶乘
    printf("5! = %d\n", factorial(5));

    // 计算 1 到 10 的和
    printf("1 + 2 + ... + 10 = %d\n", sumToN(10));

    // 打印斐波那契数列的前 10 项
    printf("\n=== 斐波那契数列前 10 项 ===\n");
    for (int i = 1; i <= 10; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");

    return 0;
}