java - 简单的递归解释

Question

这是Java中的递归静态方法。

public static int mystery(int m, int n) {
    int result = 1;   

    if (m > 0) {
      result = n * mystery(m-1, n);
    }       

    System.out.println (m + "  " + result);
    return result;
}

如果我们调用神秘（3,4）方法，标准输出会打印什么？调用神秘（3,4）的最终返回值是多少？

标准输出部分的答案的解释是什么。

输出：

0 1
1 4
2 16
3 64

最终返回值为 64。

Answer 1

Consider n to be fixed (which for all intents and purposes it is) and let f(m) be mystery(m,n).

Then

f(0) = 1
f(1) = n * f(0) = n
f(2) = n * f(1) = n * n
f(3) = n * f(2) = n * n * n

Can you see the general pattern? Can you give a closed form for f(n)?

Answer 2

鉴于您的代码是

public static int mystery(int m, int n) {
int result = 1;   

if (m > 0) {
  result = n * mystery(m-1, n);
}       

System.out.println (m + "  " + result);
return result;
}

让我们从 m = 3 和 n = 4 开始，让我们尝试通过尝试成为调试器来模拟它...

mystery(3,4){
   int result = 1
   if(3 > 0){
       result = 4 * mystery(3-1,4);
       //We proceed from this point only after evaluating mystery(2,4)
       mystery(2,4){
            int result = 1
            if(2 > 0){
                result = 4*mystery(2-1,4);
                //Now we have to evaluate mystery(1,4)
                mystery(1,4){
                    int result = 1;
                      if(1 > 0){
                          result = 4*mystery(1-1,4);
                          //Evaluate mystery(0,4)
                          mystery(0,4){
                             int result = 1;
                             if(0 > 0){
                                //Not evaluated
                             }
                             System.out.println(0 + " "+1);
                             return 1;
                          }...mystery(0,4) done continue with evaluation of mystery(1,4)
                          result = 4*1 //1 is what is returned by mystery(0,4)
                          System.out.println(1+ "" + 4);
                          return 4; 
                       }//done with the evaluation of mystery(1,4), resume evaluation of mystery(2,4)
                result = 4*4 //4 is the value returned by mystery(1,4)
                System.out.println(2 + " " + 16);
                return 16;            
                }//At this point we are done with evaluating (2,4) and on the way to resume evaluation of mystery(3,4)
       result = 4 * 16
       System.out.println(3 + " "+ 64)
       return 64;
       }
   }

希望这可以帮助

Answer 3

此示例计算 m 的 n 次方。因此，在您的情况下，该值为 64。

但是，您是否尝试过并进行了分析？

Answer 4

第一个调用是神秘（3,4），然后调用神秘（2,4），然后调用神秘（1,4），然后调用神秘（0,4）。在此示例中，基本情况是神秘（0,4），即 m > 0 的计算结果为 false 并且 result = n*mystery(m-1,n) 将不会被执行（递归在此终止）。您的基本情况位于调用堆栈的顶部，而堆栈的底部是神秘的（3,4）。从调用堆栈的顶部向底部进行评估......</p>