3

为什么递归调用后 System.out.println(res) 仍然运行？我认为它永远不会到达 System.out.println(res);

public class recursion
{
    public static void main(String[] args)
    {
        recursion p = new recursion();
        p.perms(4, "");
    }

    public void perms(int remaining, String res)
    {
        if (remaining > 0) {
           perms(remaining - 1, res + "1");
            System.out.println(res);
        }
    }
}
4

5 回答 5

8

想想步骤

call perms(4,"");                   //1 st rec
        perms(3,"1");               //2 nd rec
           perms(2,"11");           //3 rd rec
              perms(1,"111');       //4 th rec

然后因为remaining = 0它不会去如果是这样现在考虑相反的顺序

           go back to 4th rec and print 111
        go back to 3rd rec and print 11
      go back to 2nd rec and pring 1
    go back to 1st rec and print (blank space)
于 2013-05-31T08:38:04.660 回答
3

当然会的。

仔细考虑这个案例p.perms(1, "");

发生的事情是

if (1 > 0) { // this is true
    perms(0, res + "1");
    System.out.println(res);
}

并且perms(0, res + "1");是无操作的，因为它没有通过该if语句。这是您的递归块，并且您已对其进行了明智的编码。然后println执行，因为它是下一条语句。递归函数和非递归函数之间没有根本区别，尽管使用递归函数，如果重复调用它可能会耗尽堆栈空间。

对于较大的值，您可以以类似的方式取消选择递归remaining。

于 2013-05-31T08:38:53.647 回答
3

因为在最后一次递归结束时，当它没有运行时，所有先前的递归都会执行该行。递归与任何其他方法调用没有什么不同，即继续执行其他操作，但是当您完成后，在该点继续使用此方法（嗯，下一行）。

于 2013-05-31T08:35:44.020 回答
2

它会运行3次因为第四次调用后，堆栈弹出，它会回来调用

perms(remaining - 1, res + "1");

然后System.out.println(res)会运行

对于第一次调用，它将运行

CALLING ->  perms(4-1,""+"1") -> check if(3>0) ->perms(3-1,"1"+"1")-> check if(2>0) ->perms(2-1,"11"+"1") ->check if(1>0)->perms(1-1,"111"+"1")->check if(0>0)false              
STACK index ->     0                                      1                                   2                                     3               pop the stack

在堆栈中第一次弹出后，值返回到

-> 的输出 perms(1 - 1, res + "11"+"1");

将执行-> System.out.println(res);

在索引 0 之前也会发生同样的情况

于 2013-05-31T08:36:43.513 回答
0

这样解释很容易。当您执行递归调用时，函数的状态被添加到堆栈中，并且在表示基本情况（条件）时它会被反转。

例如

public class Main {

  private void printFun(int test) {
    if (test < 1) // base case
        return;
    System.out.println("Top Value : " + test);
    printFun(test - 1);
    System.out.println("Bottom Value :  " + test);
  }

  public static void main(String[] args) {
    int test = 3;
    new Main().printFun(test);
  }

}

输出将是

Top Value : 3
Top Value : 2
Top Value : 1
Bottom Value :  1
Bottom Value :  2
Bottom Value :  3

请注意，底部值从 1 开始继续，因为调用函数时测试变量的值是 1，然后继续到下一次调用，同时在递归行之后将代码反转回来。

但是，始终尝试使递归调用函数执行的最后一件事。这称为尾递归，因为编译器可以比非尾递归更好地优化它。请在https://www.geeksforgeeks.org/tail-recursion/上阅读更多关于尾递归的信息

于 2020-07-30T14:53:14.583 回答