Java 中的遞迴

要理解什麼是遞歸，首先要理解什麼是遞歸。其實要理解這些函數並沒有什麼困難，只要理解一次就可以了。並在程式設計時進行練習。 遞歸不僅出現在程式設計中，也出現在現實生活中。手裡拿著一面鏡子，站在另一面鏡子前。反射的反射會在反射中反映出來等等。你會看到無數的反射進入無窮遠。您可以在「獻給土撥鼠之日… 」一文中找到更多關於「真實」遞歸的信息，讓我們從現實世界回到程式設計師的日常生活。簡單定義：java中的遞歸函數是呼叫自身的函數。讓我舉一個非常簡單但非常有害的例子：

public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}

為什麼它有害？我建議你自己檢查一下！如果您決定進行這次冒險（您程式設計師很可能會這樣做！），請在註釋中寫下JVM 將拋出什麼錯誤=）這個範例以及許多其他範例都表明，在Java 中使用遞歸必須採用以下方法：警告。您需要了解這種解決問題的方法在何時、何地以及為何是合理的，並確保您的函數不會將程式的執行變成「土撥鼠之日」。 對於理解遞歸還有兩個更重要的定義：

• 遞歸基礎－退出遞歸呼叫區塊的條件－問題的基本解決方案，在不需要呼叫遞歸的條件下。
• 遞歸步驟是指函數在更改參數時呼叫自身。

使用遞歸函數的典型範例是計算數字的階乘。如果您忘記了，讓我提醒您：正整數N（表示為 N！）的階乘是 中的數字的乘積1 до N: N! = 1 * 2 * 3 * … (N - 1) * N。順便說一句，根據定義，零的階乘等於 1。因此，可以找到任何正整數和零的階乘（用數學語言來說 - 對於非負整數集合或自然數集合和零）。我認為您了解可以使用循環對階乘進行編程。實際上，這裡有一個非遞歸方法來解決這個問題：

private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

讓我們新增一個檢查來檢查該數字是否為正數和整數，以及一個單獨的零檢查。

private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

現在我給出遞歸解決這個問題的方法代碼：

private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

我們來看看調用的輸出結果：

System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));

我們得到期望值：

1
1
2
6
24
120
720

讓我們加入一個不錯的輸出併計算更大數字的階乘：

private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

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


System.out.println(factorial(15) + "!");

我們得到：15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! 在這種情況下，使用遞歸函數是合理且安全的。我們已經明確定義了退出遞歸區塊的條件，並且我們有信心它是可以實現的：我們輸入一個非負整數，如果該數字等於零或一，則返回結果，如果該數字更大，我們將結果乘以數字的函數n-1。以三的階乘為例：

factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1

關於使用注意事項：這個功能有什麼漏洞？如果你給一個方法一個負數作為參數，那麼檢查

if (n == 1 || n == 0) {
    return result;
}

毫無意義，我們最終會陷入一個無止盡的自我調用循環。值得添加非負性檢查：

if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}

一切都會好起來的。 一種方法相對於另一種方法有什麼優點？看似沒有太大差別，但事實上，大量的遞歸呼叫會對效能和記憶體消耗產生負面影響：呼叫堆疊是一個幾乎不可控的資源，在不同的條件下呼叫同一個遞歸函數，我們可能也會可能不會遇到與該資源相關的問題。幾乎所有使用迭代（如 的循環for-each）解決的問題也可以遞歸地解決。遞歸的優點是可讀性和書寫方便，上面我們談到了缺點：「搬起石頭砸自己的腳」的機會並不是虛無縹緲的。使用所謂的「複雜遞歸」時需要更加小心：函數A()會呼叫函數，函數B()會呼叫函數A()。解決此類問題需要充分理解遞歸的工作原理。此類任務的範例：計算 的值x^n/(n!)。正如我們上面所討論的，階乘是在非負整數集合上定義的。最後我給出解決方案代碼。複雜的遞歸將包含兩種方法：

private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

要進入遞歸，需要使用一個方法calculate，該方法呼叫一個方法power，該方法又呼叫一個方法calculate。我們在冪法中定義了遞歸基礎：

if (n == 1) return x;

遞歸步驟也在那裡定義：

return x * calculate(x, n - 1);

剩下的就是增加輸入資料有效性的檢查：

• 零以外的任何數字都等於零的冪1。如果n = 0，那麼n! = 1。需要退貨1。
• 零的任一冪都等於零。
• 我們不會考慮類型不確定性0^0，並將接受此類輸入資料為無效資料。

通過所有檢查，方法將如下所示：

private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

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

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

好吧，當呼叫函數時，你需要記住捕獲錯誤：

try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}