C中的递归函数取3到另一个数的幂

我想在C中写一个递归函数来取3的值到另一个数的幂。例如，如果我输入4，程序将返回值81.下面的代码是问题的答案。但我无法清楚地理解代码如何解决问题。我的意思是，当4传递给函数时，函数体中的前3行将被忽略，直接跳入“//这行”。那么它是如何从程序返回数字81的。该函数再次以3通过自我调用？ 3 * three_power（3）？我无法清楚地理解这一点。有人可以解释吗？对不起，因为这是一个愚蠢的问题，我是新来的C.C中的递归函数取3到另一个数的幂

#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 
}

来源

2016-02-19 Minh

这是你从调试器中看到的吗？程序并不是真正跳过前三行，只是它们已经被优化，调试器无法正确地跟踪它们。尝试在没有优化的情况下重新编译，然后再启动调试会话，您甚至会看到前三行...... –

'return'不是一个函数，而是一个声明。你不应该在结果周围添加括号。他们不是陈述的一部分，但表达和不必要的。 – Olaf

“*要理解递归，您需要了解递归... *”;-) – alk

是的，它需要通过第一种方式，这会导致对4 - 1递归调用再次采取else分支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()。

来源

2016-02-19 13:52:54 unwind

非常感谢！我现在可以理解它。谢谢！！ – Minh

@Minh很高兴帮助。当然，请随时接受答案。 :) – unwind

考虑编写显示每个入口和出口的命令流程。其他人的回报也是其他的一行。我会重写它显示正确的括号。

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; 
}

来源

2016-02-19 13:56:18 sabbahillel

这是递归的本质。在数学意义上，可以将3^n的幂定义为3 * 3 ^（n-1），对吗？毕竟3到任何东西都是3倍的次数本身，对吧？

递归只是说“权力3是什么？”的答案。那么它是三倍于功率的三倍。当功率为0时，您只需处理这种情况，返回的值将乘以递归调用的次数乘以3。

这是一个很好的学习锻炼，但你应该更喜欢POW（3，功率），因为它是更有效的计算这样的，你不这样做的风险超过最大递归调用堆栈。

来源

2016-02-19 13:56:34 Neil

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

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

这是递归，其类似于感应的数学概念的一个例子。对于一个给定的输入，它将自己调用一个减少的输入，然后使用该结果产生所需的结果。

的一个好方法，了解功能的工作原理是用最简单的情况开始，确认它可以工作，然后移动到下一个简单的情况下，等

在这个例子中，最简单的情况是，当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的正确结果。只有当结果变得足够大时才会失败。

来源

2016-02-19 14:14:38

我会提出一个更高效的递归比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))。

来源

2016-02-19 14:39:39

C中的递归函数取3到另一个数的幂

回答

相关问题