0

我是递归的新手，我仍然对这个问题感到困惑。

这是代码

 public class TestRecursion { 
 public static void main(String[] a) { 
 System.out.println(Recurse("Yes", 1)); 
 } 

 public static String Recurse(String s, int n) { 
 if (n < 5) 
 return s+Recurse(s + n, n + 1); 
 else 
 return "End"; 
 } // end Recurse() 
}

所以这个问题的答案是：

YesYes1Yes12Yes123End

问题是为什么当我切换返回时“结束”首先打印

 return Recurse(s + n, n + 1) + s;

注意 s 现在在递归之后

结果如下：

EndYes123Yes12Yes1Yes
4

3 回答 3

1

"End" 放置在评估字符串最后一部分的位置。当你做s + recurse最后一部分时，最后评估。当你这样做时recurse + s，开始最后评估。

于 2013-10-27T21:08:14.310 回答
1

请注意，递归可以在树结构（所谓的递归树）中最好地可视化。您通常有终端（在您的情况下，s）和非终端（进一步的函数调用，即Recurse）。使用 draw.io（网站），我快速创建了这个图表来说明以下情况Recurse(s + n, n + 1) + s：

递归树

你总是从左到右评估。看看如果你在每一步切换终端和非终端的顺序会发生什么：垂直镜像图像，然后再次从左到右评估。

于 2013-10-27T21:26:34.843 回答
1

让我们抓住虚拟纸并解决这个问题：

public class TestRecursion { 
  public static void main(String[] a) { 
    System.out.println(Recurse("Yes", 1)); 
  } 

  public static String Recurse(String s, int n) { 
    if (n < 5) 
      return s+Recurse(s + n, n + 1); 
    else 
     return "End"; 
  } // end Recurse() 
}

好的，现在从头开始：

n     S           s+Recurse(s+n, n+1)
1     Yes         "Yes" + Recurse ("Yes1", 2)
2     Yes1        "Yes1" + Recurse ("Yes12", 3)
3     Yes12       "Yes12" + Recurse ("Yes123", 4)
4     Yes123      "Yes123" + Recurse ("Yes1234", 5)
5     Yes1234     "End" <- Here we go to the else block

因此，当我们展开堆栈时，我们得到：

n     S           s+Recurse(s+n, n+1)
5     Yes1234     "End" <- Here we go to the else block
4     Yes123      "Yes123" + "End"
3     Yes12       "Yes12" + "Yes123End"
2     Yes1        "Yes1" + "Yes12Yes123End"
1     Yes         "Yes" + "Yes1Yes12Yes123End"

所以，我们最终得到YesYes1Yes12Yes123End

现在，让我们改变方法：

public class TestRecursion { 
  public static void main(String[] a) { 
    System.out.println(Recurse("Yes", 1)); 
  } 

  public static String Recurse(String s, int n) { 
    if (n < 5) 
      return Recurse(s + n, n + 1) + s; 
    else 
     return "End"; 
  } // end Recurse() 
}

好的，现在从头开始：

n     S           Recurse(s+n, n+1) + s
1     Yes         Recurse ("Yes1", 2) + "Yes"
2     Yes1        Recurse ("Yes12", 3) + "Yes1"
3     Yes12       Recurse ("Yes123", 4) + "Yes12"
4     Yes123      Recurse ("Yes1234", 5) + "Yes123"
5     Yes1234     "End" <- Here we go to the else block

现在，当我们展开堆栈时，我们最终得到：

n     S           Recurse(s+n, n+1) + s
5     Yes1234     "End" <- Here we go to the else block
4     Yes123      "End" + "Yes123"
3     Yes12       "EndYes123" + "Yes12"
2     Yes1        "EndYes123Yes12" + "Yes1"
1     Yes         "EndYes123Yes12Yes1" + "Yes"

所以，我们终于得到EndYes123Yes12Yes1Yes

于 2013-10-27T21:14:41.633 回答