調用自己的方法..遞歸？

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。再加上一個是最頂級的電話。這是一般的答案。