调用自己的方法..递归？

Question

public static int m(int i, int j)  
{  
    if (i > j)  
    return 0;  
    else  
    { 
    i++;  
    m(i++, j); 
    } 
    return i;  
} 

我有两个问题。 1.）out.print(m(3,8));和2）返回的是什么。）被调用的方法有多少次？答案应分别为5和7。

当我研究问题1时，我出来了5，但我做的方式是不正确的，因为该方法没有被调用7次，它只被调用两次。我这样做的方式是，我直接去了else语句，因为(i > j)在开始时是错误的，并且此时再次调用方法m，因为这个时候我再次调用了(4, 8)我认为它仍然是错误的，所以我回到了调用m的行和变量由于m(i++, j)中的i++，我改为5。之后，它将返回5为我的价值。

这显然是错误的，所以我在整个程序中为我的值添加了一些out.prints，看看值是如何变化的，它从方法m开始的out.print(i);从3变为9。在return i;之前的out.print(i);显示值开始从10向后倒5，并且该方法被称为7次。这个怎么用？

编辑：记录后，我能够想出一些逻辑，但我希望有人澄清它是正确的。

方法m在开始时用3,8调用。之后，它将自己调用4,8和5,8 ....直到9,8，其中if语句变为true并且方法返回0.它自己调用了6次，所以它开始向后或向下6次因为m（i ++，j）是post（i），所以我变成了10并且返回了10，然后是9，然后是8，然后是7，6，最后是5.当它返回10时是1，9是2，8是3，7是4，6是5，5是6.所以，当i = 5时是6，那是返回的值。它是否正确？如果是这样，更深入的解释将是很好的。

Answer 1

为了更好地了解发生了什么，这可能有助于重构代码这样：

public static int m(int i, int j) { 
    static int calls = 0;  
    System.out.println("entering. count: " + calls); 
    calls++; 

    System.out.println("i = " + i); 
    System.out.println("j = " + j); 

    if (i > j) { 
     System.out.println("returning 0"); 
     return 0; 
    } else { 
     i++;  
     m(i++, j); 
    } 

    System.out.println("returning " + i); 
    return i;  
} 

请注意，我没有修改过任何实际的逻辑。我所做的只是添加一些语句来打印值，以及一个变量来跟踪调用方法的次数。

Answer 2

你看到值减少的原因是因为在你打印最后一个'i'之前，这个值只会在局部范围内（第一个i ++在你的其他情况下）增加。

当你的m函数返回给调用者时，i不再是i + 1，因为它在孩子中，因此你会看到递减值，直到返回根m。

Answer 3

我会在一般情况下分析函数，具体的参数值只会在最后使用。运行该函数并通过调试器或调试打印来查看它的功能时很方便，但在某些情况下，您只能依靠大脑。例如。从（您需要模拟其工作）拉取调试信息非常困难。在面试工作时，通常需要一台计算机来测试代码 - 分析技能正在测试中。这就是为什么我强烈建议使用铅笔&纸张方法，然后再查看代码在执行时的真实含义。

问题1：返回值

当试图分析复杂的代码，知道什么可以忽略是成功的关键。

在这里，你知道

• 代码是单线程的，
• 没有全局变量，没有副作用当前呼叫之外的世界，递归的
• 返回值通话不被使用。

所以没有必要去想什么乱七八糟可能来自其他线程，你可以分析单个呼叫而不如何递归调用会（从返回值开）影响它的思维，你可以对忘记递归调用，除非它是无限递归（不会让程序终止），因为它没有其他消耗时间的效果。

递归不是无限的，因为在递归调用之前i总是递增，并且当i > j时递归停止。

知道了，决定返回值是多么容易。该功能可以降低到

public static int m(int i, int j) 
{ 
    if (i > j) 
     return 0; 
    else 
     i += 2; 
    return i; 
} 

因为回报终止函数的执行，这可以进一步降低至

public static int m(int i, int j) 
{ 
    return (i > j) ? 0 : i + 2; 
} 

给你回答问题1时称为m(3, 8)，结果是0，因为i小于j。

问题2：电话

递归数是线性的 - 最多一个递归调用每个调用。所以你必须计算在达到递归底部之前需要多少次调用。

递归的底部是条件的第一个分支。因此，您需要统计一次呼叫的次数，直到i > j。

j在每个调用中具有相同的值。没有命令来改变它的值，它总是不变地传递给递归调用。 i在递归调用之前和调用一次之后总是递增（i++是后增量，在使用原始值后生效）。只有第一个增量与递归调用相关。

计数递归调用的缘故，该功能可以降低到

public static void m(int i, int j) 
{ 
    if (i > j) 
     return; 
    else 
     m(i + 1, j); 
} 

由此看来，很明显，i依次递增1，直到它比j更大。

在m(3, 8)，调用是

• m(3, 8)，
• m(4, 8)，
• m(5, 8)，
• m(6, 8)，
• m(7, 8)，
• m(8, 8)和
• m(9, 8)。

所以有7个。

如果给出的参数有较大的差异，通用的解决方案将是方便的。所以我们来探讨一下。它会很快。

如果最初是i > j，显然只有一个呼叫。否则......从i到j + 1的数从几个到数？ (j + 1) - i + 1 = j - i + 2。再加上一个是最顶级的电话。这是一般的答案。