递归的基本思想

什么是递归：

通常，递归是函数直接或间接调用自身的时间。例如：

// This method calls itself "infinitely"
public void useless() {
    useless();  // method calls itself (directly)
}

将递归应用于问题的条件：

使用递归函数解决特定问题有两个前提条件：

1. 问题必须有一个基本条件，它将是递归的端点。当递归函数达到基本条件时，它不再进行（更深）递归调用。

2. 每个级别的递归都应该尝试一个较小的问题。因此递归函数将问题分成越来越小的部分。假设问题是有限的，这将确保递归终止。

在 Java 中有第三个前提条件：没有必要过于彻底地解决问题; 在 Java 中看到深度递归是有问题的

例

以下函数使用递归计算阶乘。注意方法 factorial 如何在函数内调用自身。每当它调用自身时，它将参数 n 减少 1.当 n 达到 1（基本条件）时，函数将不再递归。

public int factorial(int n) {
    if (n <= 1) { // the base condition 
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

这不是计算 Java 中因子的实用方法，因为它没有考虑整数溢出，或者对于 n 的大值调用堆栈溢出（即 StackOverflowError 异常）。