递归函数 - 为什么不是无限循环？

所以这显然是一个有效的代码位，但我无法弄清楚如果exponent参数是除0之外的任何参数，第二次调用power是如何完成的。递归函数 - 为什么不是无限循环？

function power(base, exponent) { 
    if (exponent == 0) 
    return 1; 
    else 
    return base * power(base, exponent - 1); 
}

来源：http://imgur.com/Sa2BfHJ

来源

2013-11-15 max pleaner

请在问题本身中包含有效的代码，并且对所有持有神圣的爱都不要使用代码的屏幕截图。 ** –

编辑注意：[编辑问题]（http://stackoverflow.com/revisions/19992274/3）不是建议修改代码段的正确方法。发布它作为答案的一部分。 –

那么，当你用除指数的正整数之外的其他东西调用它时，它*是*无限循环（或更好：堆栈溢出）。 – Bergi

因为第二个电话会跟上指数更小的数字呼叫，直到它到达0，然后返回1，并回滚汇总结果...

我认为你必须做递归:)

一些阅读下面是它如何会看一个简单的例子：

power(2,2) 
power(2,1) 
    power(2,0) 
     return 1 
    return 2*1 = 2 
return 2*2 = 4

采取和修改从这page。

试试这个页面an animated view of the recursion（我没有工作，这是一个旧的一页，需要Java，我没有它我的机器上安装了...）

编辑：
它困扰着我，我找不到这样的任何简单的例子，这里有一个快速的控制台程序，可以帮助你想象这是如何工作的：

using System; 
using System.Collections.Generic; 
using System.Globalization; 
using System.Linq; 
using System.Text; 
using System.Threading; 
using System.Threading.Tasks; 

namespace SO_Console 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      int base_value = 0; 
      int exponent = 0; 
      string[] parts = new string[2]; 
      int result = 0; 
      Console.Out.WriteLine("Please enter the Power to calculate in this format: x^y " 
      + Environment.NewLine + "(where x is the base (int) and y is the exponent (int)." 
      + Environment.NewLine); 

      var temp = Console.ReadLine(); 
      if (!string.IsNullOrWhiteSpace(temp)) 
      { 

       parts = temp.Split('^'); 
       if (parts.Length != 2) 
       InvalidInput(); 
      } 
      else 
      InvalidInput(); 


      if (Int32.TryParse(parts[0], out base_value) && Int32.TryParse(parts[1], out exponent)) 
      result = Power(base_value, exponent, ""); 
      else 
      InvalidInput(); 

      Console.Out.WriteLine(Environment.NewLine + "Final result = {0}", result); 


      Console.Out.WriteLine(Environment.NewLine + "Hit any key to quit."); 
      Console.Read(); 

     } 

     /// <summary> 
     /// Recursive call to calculate Power x^y 
     /// </summary> 
     /// <param name="base_value">The base</param> 
     /// <param name="exponent">The exponent</param> 
     /// <param name="padding">Padding, for output.</param> 
     /// <returns></returns> 
     private static int Power(int base_value, int exponent, string padding) 
     { 
      Console.Out.WriteLine(string.Format("{2}Power called with: {0}^{1}", base_value, exponent, padding)); 
      Thread.Sleep(750); 

      if (exponent == 0) 
      { 
       Console.Out.WriteLine("{0}{1}Base case reached, returning 1.{0}", Environment.NewLine ,padding); 
       return 1; 
      } 
      else 
      { 
       var return_value = base_value * Power(base_value, exponent - 1, padding + " "); 
       Console.Out.WriteLine("{0}Going back in the recursion, returning {1}.", padding, return_value); 
       Thread.Sleep(750); 
       return return_value; 
      } 
     } 

     /// <summary> 
     /// Inform user about bad input and quit. 
     /// </summary> 
     private static void InvalidInput() 
     { 
      Console.Out.WriteLine("Invalid input."); 
      return; 
     } 
    } 
}

您只需粘贴和运行它，你的结果将沿着看起来：

outputsamuple

编辑2：
我写这个文章，详细解释发生了什么，为什么在那里。欢迎您来看看这里：simple power recursion, console application。

来源

2013-11-15 02:13:27 Noctis

+1加倍努力。 – Gjeltema

观察是x ^Ñ = X × X ^n-1个且x = 1。这就是为什么代码是正确的。

来源

2013-11-15 02:16:14

只是尝试一个例子。这里有2至3

power(2,3) = 2 * (power(2,2) = 2 * (power(2,1) = 2 * (power(2,0) = 1)))

所以功率：

power(2,3) = 2 * (2 * (2 * 1)))

来源

2013-11-15 02:16:30 rjsang

递归只有终止，当你有edge case。在求幂的情况下，边缘的情况是：

Ñ = 1

它读取作为“升高至0功率的任何数目是1”。

幂的一般情况是：

Ñ^X =正×Ñ^{X - 1}

在象Haskell求幂数学语言将被定义如下：

n^0 = 1 
n^x = n * n^(x - 1)

有意思的是，如果你给这个函数一个负整数，那么边缘条件将永远不会执行，并且它将运行到一个无限循环，最终以堆栈溢出终止。

但是，由于我们只对整数（0和正整数）使用此函数，因此您将永远不会遇到无限循环。

但是，如果您使用足够大的指数，您仍然会遇到堆栈溢出，因为计算机只有足够的空间来存储中间结果。

在大多数JavaScript的浏览器，你可以计算2^2^14。但是，如果你尝试计算2^2^15，那么你会发现堆栈溢出：http://jsfiddle.net/9chrJ/

来源

2013-11-15 02:42:16

递归函数 - 为什么不是无限循环？

回答

相关问题