在C语言中编写递归函数来计算3的另一个数次幂

Question

我正在尝试用C语言编写一个递归函数，将3的幂值返回给其他数字。例如，如果我输入4，程序将返回值81。下面的代码是问题的答案。但我不能清楚地理解这段代码如何解决这个问题。我的意思是，当4被传递到函数中时，函数体中的前3行将被忽略，直接跳到“// This line”。然后从那里，程序如何返回数字81呢？函数再次调用自己并传递3吗？是3*three_power(3)吗？我无法清楚地理解这一点。有人能解释吗？对不起，这是一个愚蠢的问题，我是C语言的新手。

#include <stdio.h>
int three_power(int power);
int main(){
    int a=4;
    int b=9;
    printf("\n3 to the power of %d is %d", a, three_power(a));
    printf("\n3 to the power of %d is %d", b, three_power(b));
    return 0;
}
int three_power(int power){
    if (power < 1){
        return( 1 );
    } else
    return (3* three_power(power-1));  //This line
}

- Minh

---

这是你从调试器中看到的吗？程序并没有真正跳过前三行，只是它们已经被优化掉了，调试器无法正确地跟踪它们。在开始调试会话之前尝试重新编译而不进行优化，你将会看到前三行... - Frankie_C

return不是一个函数，而是一个语句。你不应该在结果周围添加括号。它们不是语句的一部分，而是表达式，也是不必要的。 - too honest for this site

"要理解递归，你需要理解递归...";-) - alk

Answer 1

是的，在第一次执行时，它会进入else分支，导致对4-1进行递归调用，然后再次进入else分支，以此类推，直到基本情况，当power为0时，它只返回1（因为3⁰等于1）。

完整的链路如下：

3 * three_power(3) =
3 * (3 * three_power(2)) =
3 * (3 * (3 * three_power(1)) =
3 * (3 * (3 * (3 * three_power(0))) =
3 * (3 * (3 * (3 * (1)))) =
3 * 3 * 3 * 3 = 81

虽然很难想象，但事实就是这样。

当然，您可以通过调试器逐步执行来了解它的工作原理，或者只需将printf("power=%d\n", power); 添加到 three_power() 函数的第一行即可。

- unwind

---

非常感谢！！我现在明白了。谢谢！！ - Minh

@Minh 很高兴能帮忙。当然，随时欢迎接受答案。 :) - unwind

Answer 2

这就是递归的本质。

从数学角度来看，可以将3^n的幂定义为3 * 3^(n - 1)，对吗？毕竟3的任何幂次方都是3自己乘以相同次数的结果，对吗？

递归只是简单地表明了“什么是3的幂？”嗯，它是3乘以power减一次幂的三次幂。你只需要处理当power为0时的情况，返回值将被递归调用的数量乘以3。

这是一个非常好的学习练习，但你应该更喜欢pow(3, power)，因为这种方式更有效率，而且不会有超出最大递归调用栈的风险。

- Neil

---

我认为他只是通过这种方式学习递归。我不认为他会真正使用它（:-) - sabbahillel

@sabbahillel 我同意，但我主要提到这一点是为了防止专业程序员看到此页面并认为使用递归来查找数字的幂是一个好主意。 - Neil

Answer 3

这是递归的一个例子，类似于数学归纳的概念。对于给定的输入，它在减少的输入上调用自身，然后使用该结果生成所需的结果。

理解函数如何工作的好方法是从最简单的情况开始，验证它是否有效，然后继续下一个最简单的情况，以此类推。

在这个例子中，最简单的情况是当power为0时。在这种情况下，它立即返回1。到目前为止还不错。

现在考虑当power为1时会发生什么。在这种情况下，它返回3 * power(0)。换句话说，它使用不同的输入调用自身，然后使用该结果生成新的结果。我们已经验证了power(0)返回1。因此，在这种情况下，它将返回3 * 1，即3。同样，到目前为止还不错。

当power是2时会发生什么？好的，它会返回3 * power(1)。这将导致多个嵌套调用。我们知道power(1)将返回3，因此此情况将返回9。再次说明，它正在执行我们想要的操作。

更一般地，当power大于等于1时，它会递归调用自身以获得power - 1的结果。这通常会导致一系列调用，最终返回所需的power - 1结果。然后将其乘以3并返回结果。这是3 * (3 ** (power - 1))，就是我们想要的3 ** power。

你可以通过归纳法来确认它的正确性。基本情况是当power为0时。这种情况可以直接确认。然后，假设它对power - 1给出了正确的结果，我们可以从递归步骤中看到它也会对power给出正确的结果。只有当结果变得足够大而溢出时，它才会失败。

- Tom Karzes

Answer 4

考虑编写命令流图，显示每个示例的输入和输出。 否则返回是单行否则。 我将重新编写它，显示正确的括号。

1e. 输入值为4

2e. 输入值为3

3e. 输入值为2

4e. 输入值为1

5e. 输入值为0

5r. 返回1

4r. 返回3*5r = 3*1 = 3

3r. 返回3*4r = 3*3 = 9

2r. 返回3*3r = 3*9 = 27

1r. 返回3*2r = 3*27 = 81

int three_power(int power)
{
    if (power < 1)
    {
        return( 1 );
    }
    else
    {
        return (3* three_power(power-1));  //This line
    }
}

使用单个返回语句来表达它的另一种方式是

int three_power(int power)
{
    int rtnval;
    if (power < 1)
    {
        rtnval = 1;
    }
    else
    {
        rtnval = 3* three_power(power-1);  //This line
    }
    return rtnval;
}

- sabbahillel

Answer 5

我建议使用比 f(n)=3*f(n-1) 更高效的递归。

它应该是：

// f(n) = 1 if n = 0
// f(n) = f(n/2)^2` if n is even
// f(n) = 3*f(n/2)^2 if n is odd

int power3(int n)
{
    int m;
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
    {
        m = power3(n/2);
        return m*m;
    }
    else
    {
        m = power3(n/2);
        return 3*m*m;
    }
}

这样时间复杂度由 O(n) 降低到了 O(log(n))。

- Eugene Sh.