在Java因子程序中遞歸

我對遞歸的瞭解是，函數自己調用，它有停止的基本條件。我的教授編寫了一個程序，他稱這個程序正在發生遞歸，我說不，它不是。我對此感到困惑。所以我要求你澄清我的困惑。他編寫的程序如下代碼：在Java因子程序中遞歸

int fact(int n) { 
    if (n == 0) { 
     return 1; 
    } 

    for (int i = n; i >= 1; i--) { 
     s1.push(i); 
    } 
    return Return_result(); 

} 

int Return_result() { 
    int f = 1; 
    while (s1.top != -1) { 
     f = f * s1.pop(); 
    } 
    return f; 
}

來源

2014-11-08 Aj Jadoon

它不是。 'Return_result（）'不會調用它自己，堆棧函數'push（）'和'pop（）'也不是遞歸的。迭代和遞歸不是一回事。 – hfontanez 2014-11-08 14:10:59

首先我要解釋一些事實：

階乘是由以下公式計算：n! = n * n-1 * n-2 * n-3 * .....* 3 * 2 * 1
堆棧工作在LIFO = last in first out或FILO = first in last out

所以代碼執行以下操作它首先將所有從n到1的數字放在一個堆棧中，然後彈出每個數字並將其與當前結果相乘，以得到最終的階乘

，並通過對階乘（非遞歸）迭代版本的方式，遞歸版本會像下面

int fact(int n) 
{ 
    int result; 

    if(n==1) 
    return 1; 

    result = fact(n-1) * n; 
    return result; 
}

來源

2014-11-08 14:08:29

你是對的，在所提供的代碼中沒有遞歸。這是一種迭代方法。

遞歸是，如果在f()方法（Java命名法）或函數（一般）中，您可以調用f()。

遞歸的方法將是這樣的：

int fact(int n) { 
    return (n <= 1) ? 1 : fact(n - 1) * n; 
}

或者，使用tail-recursion（也被稱爲「尾調用」）：

int fact(int n) { 
    return factTail(n, 1); 
} 

int factTail(int n, int accumulator) { 
    return (n <= 1) ? accumulator : factTail(n - 1, n * accumulator); 
}

目前，JVM不執行尾遞歸優化，但this can change：

重要的是要注意，這不是JVM中的錯誤。這是一個優化，可以實現以幫助使用遞歸的功能程序員，這在語言中更加普遍和正常。我最近在Oracle上與Brian Goetz談到了這個優化問題，他說這是一個要添加到JVM的的列表，但它不是一個高優先級的項目。目前，最好是自己進行此優化，如果可以的話，在JVM上編寫功能語言時，避免使用遞歸函數。

來源

2014-11-08 14:07:04

在Java因子程序中遞歸

回答

相關問題