C语言编程题使用递归计算一个整数的阶乘

计算一个整数的阶乘是一个经典的递归问题。递归是解决阶乘问题的一种优雅方法,但需要注意递归的深度和边界条件。阶乘(factorial)是数学上一个重要的概念,表示所有小于及等于该数的正整数的积。用符号“!”表示。

1、直接递归

最直接的递归实现方式。

#include <stdio.h>

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

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

2、尾递归

尾递归是一种优化的递归方式,其中递归调用是函数的最后一步操作。

#include <stdio.h>

int tail_factorial(int n, int accumulator) {
    if (n == 0) {
        return accumulator;
    } else {
        return tail_factorial(n - 1, n * accumulator);
    }
}

int factorial(int n) {
    return tail_factorial(n, 1);
}

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

3、三元运算符递归

使用三元运算符来简化代码。

#include <stdio.h>

int factorial(int n) {
    return (n == 0) ? 1 : n * factorial(n - 1);
}

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

4、递归的分治法

通过分治法来计算阶乘,可以将大问题分解为更小的问题。

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) {
        return 1;
    } else if (n % 2 == 0) {
        int half_factorial = factorial(n / 2);
        return half_factorial * half_factorial * (n / 2) * (n / 2 + 1);
    } else {
        return n * factorial(n - 1);
    }
}

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

5、递归的内存优化

通过动态编程思想,减少重复计算来优化内存使用。

#include <stdio.h>

int factorial(int n, int memo[]) {
    if (n == 0) {
        return 1;
    }
    if (memo[n] != 0) {
        return memo[n];
    }
    memo[n] = n * factorial(n - 1, memo);
    return memo[n];
}

int main() {
    int num = 5;
    int memo[6] = {0}; // 这里memo大小设置为 num+1
    printf("Factorial of %d is %d\n", num, factorial(num, memo));
    return 0;
}

推荐阅读
cjavapy编程之路首页