C++遞歸問題

Question

我覺得有點啞問這個，但在這裏我們去...

當試圖遵循以下網站的遞歸的例子，我遇到了有我困惑的道路隆起。

我改變了代碼略微只是爲了讓我的頭在代碼遞歸的例子，我幾乎有我的頭，但我無法弄清楚爲什麼變量'n'遞增'通過B'當我沒有告訴程序增加'n'時。

請你幫忙解釋一下嗎？

#include <stdlib.h> 
#include <iostream> 

using namespace std; 

long factorial (long n) 
{ 
    if (n > 1) 
{ 
    long r(0); 
    cout << "Pass A" << endl; 
    cout << "n = " << n << endl; 
    cout << "r = " << r << endl; 

    r = n * factorial (n-1); 

    cout << "Pass B" << endl; 
    cout << "n = " << n << endl; 
    cout << "r = " << r << endl; 
    return (r); 
} 
    else 
    return (1); 
} 

int main() 
{ 
    long number; 
    cout << "Please type a number: "; 
    cin >> number; 
    cout << number << "! = " << factorial (number) << endl; 
    system ("pause"); 
    return 0; 
} 

Answer 1

你看，爲了所有的「傳遞」 -s，然後所有的「通行證B」中，給人的感覺是n的增量雖然你們看到的只是最初傳遞個n相反的順序-s。

Answer 2

在我看來，你的程序正常工作，應該輸出像這樣的數= 3（爲便於閱讀，換行刪除）：

傳遞N = 3，R = 0 [1]

傳遞一個n = 2的R = 0 [2]

通行證乙n = 2時R = 2 [3]

通行證乙n = 3的R = 6 [4]

所以我認爲可以看看你會如何得出結論在通過B中n正在遞增，但事實上並非如此。 您需要記住，n是一個函數局部變量，因此在這種情況下，[3]中打印的n是局部變量的一個不同實例，與[4]中的n相同。

[1]和[4]中打印的n的值來自函數的頂部調用（其中n = 3），[2]和[3]中打印的值是頂級版本中的調用的因素（即n-1）。

Answer 3

如果您注意到，傳遞B並不是真的第二次通過函數，它只會打印遞歸的結果。

所以打印4，3，2，等等，而backwords片B印片4 3 2 1（即2 3 4）

Please type a number: 4 
Pass A 
n = 4 
r = 0 
Pass A 
n = 3 
r = 0 
Pass A 
n = 2 
r = 0 
Pass B 
n = 2 
r = 2 
Pass B 
n = 3 
r = 6 
Pass B 
n = 4 
r = 24 
4! = 24 
Press any key to continue . . . 

嘗試更換第二R打印爲

cout << "Pass B" << endl; 
    cout << "n = " << n << endl; 
    cout << "r = " << r << " --- NOTICE RESULT ACCUMULATING AS WE UNNEST THE RECURSION" <<endl; 

PS C:\temp> .\r.exe 4 
Please type a number: 4 
Pass A 
n = 4 
r = 0 
Pass A 
n = 3 
r = 0 
Pass A 
n = 2 
r = 0 
Pass B 
n = 2 
r = 2 --- NOTICE RESULT ACCUMULATING 
Pass B 
n = 3 
r = 6 --- NOTICE RESULT ACCUMULATING 
Pass B 
n = 4 
r = 24 --- NOTICE RESULT ACCUMULATING 
4! = 24 
Press any key to continue . . . 

Answer 4

那是因爲你是遞歸的unrolling。

你是不是真的增加n你只是回到以前的函數調用其中n是n+1你叫factorial(n-1)前...

當你開始你上去

r = n * factorial (n-1); 

這將導致另一個函數調用factorial。

你繼續這樣做（從功能開始啓動，至多到調用factorial與n減1），直到你最終在函數調用結束到factorial地方n<=1。

在這種情況下你返回1，但是你返回到n是2，你做乘法（n * whatever was returned by factorial）階乘以前的呼叫，並完成該呼叫的B路徑並返回r。

但你再次返回到前一個函數調用，你做乘法部分並完成B路徑等等...

factorial(5) 
    factorial(4) 
    factorial(3) 
     factorial(2) 
     factorial(1) 
     return 1 
     return r 
    return r 
    return r 
return r 

Answer 5

通B時的它是「平倉」遞歸打印。它遞歸直到它碰到「else return（1）;」部分，然後開始退出。因爲它在每次進入的時候都會以n減少n，所以它在退出時似乎正在增加。

Answer 6

n的通過值A和通過B將永遠是相同的，因爲你不會在兩者之間的任何地方改變它。您將n-1傳遞給遞歸調用，但不會更改n的值。

您可能會感到困惑的原因是您沒有看到通過A並通過B爲給定的n (n>2)彼此相鄰。

When n=2, you'll see: 
pass A for n=2 
pass B for n=2 

When n=3, you'll see: 
pass A for n=3 
pass A for n=2 // cuz of recursive call. 
pass B for n=2 
pass B for n=3 // looks like n has increment here..but this 'pass B' pairs with first pass A 

Answer 7

因爲那是遞歸倒回的時候。

也許在n爲2時考慮這種情況會更容易。在這種情況下，您需要輸入條件塊並在「傳遞A」後進行遞歸。當你遞歸n是1，所以你通過else塊返回。當您返回時您返回遞歸的前一幀，其中n爲2. r根據遞歸調用的結果得到更新2*1，但n保持2與前一幀一樣。

factorial(2) 
    factorial(1) 
factorial(2) 

如果n起初將任何較大的值，那麼你會保持復卷和n將它的值恢復到它有每個遞歸之前，每個值。

factorial(3) 
    factorial(2) 
    factorial(1) // returns 1 
    factorial(2) // r=2*1 
factorial(3)  // r=3*2 

Answer 8

有些答案使用縮進，使之更容易理解發生了什麼 - 你的情況下使用相同的效果，使自己的調試輸出更容易理解： 試着改變你的函數是這樣的：

long factorial (long n, std::string prefix= "") // default parameter 
    ... 
    cout prefix << "Pass A" << endl; 
    cout prefix << "n = " << n << endl; 
    cout prefix << "r = " << r << endl; 

    r = n * factorial (n-1, prefix+ " "); // increase indentation 
    ...etc... 

我對std :: string的使用可能有點片狀，但你會明白。你的輸出現在應該看起來像這樣。

Please type a number: 4 

Pass A 
n = 4 
r = 0 
    Pass A 
    n = 3 
    r = 0 
    Pass A 
    n = 2 
    r = 0 
    Pass B 
    n = 2 
    r = 2 
    Pass B 
    n = 3 
    r = 6 
Pass B 
n = 4 
r = 24 

4! = 24