用递归方法求x的n次方

递归是一种解决问题的技术，常用于计算复杂数据结构或数学序列，如计算数字的幂。用递归方法求一个数 `x` 的 `n` 次方可以这样实现：

#include <stdio.h>

// 递归函数计算 x^n
double power(double x, unsigned int n) {
    if (n == 0) { // 递归的基本情况：0次幂等于1
        return 1;
    } else if (n % 2 == 0) { // 如果 n 是偶数，则简化为 (x^(n/2))^2
        return power(x, n / 2) * power(x, n / 2);
    } else { // 如果 n 是奇数，则简化为 x * (x^(n-1))
        return x * power(x, n - 1);
    }
}

int main() {
    double base = 2; // 例如我们计算 2 的幂
    unsigned int exponent = 5; // 要求的次方
    double result = power(base, exponent);
    printf("2 to the power of %u is %.15f\n", exponent, result);
    return 0;
}

在这个递归函数中，如果 `n` 为0，返回1；否则，根据 `n` 是否为偶数选择不同的分支，直到达到基本情况。

相关问题

c语言使用递归求x的n次方

以下是两个使用递归求x的n次方的C语言例子：

1. 使用函数pow()递归求解

#include <stdio.h>

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

int main() {
    int x, n, ret;
    printf("请输入x，n:\n");
    scanf("%d %d", &x, &n);
    ret = pow(x, n);
    printf("求得%d的%d次幂为%d\n", x, n, ret);
    return 0;
}

2. 在main()函数中递归求解

#include <stdio.h>

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

int main() {
    int x, n, sum;
    printf("请输入x，n:\n");
    scanf("%d %d", &x, &n);
    sum = pow(x, n);
    printf("求得%d的%d次幂为%d\n", x, n, sum);
    return 0;
}

使用递归函数求x的n次方

可以使用如下递归函数求x的n次方：

def power(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return power(x**2, n//2)
    else:
        return x * power(x**2, (n-1)//2)

这个函数的思路是：

- 如果n等于0，返回1（任何数的0次方都是1）。
- 如果n是偶数，返回x的n/2次方的平方。
- 如果n是奇数，返回x乘以x的(n-1)/2次方的平方。

这个递归函数的时间复杂度是O(log n)，因为每次递归都将指数减半。