Java 递归

Java 递归

递归是进行函数调用本身的技术。这种技术提供了一种将复杂问题分解为更容易解决的简单问题的方法。

递归可能有点难以理解。弄清楚它是如何工作的最好方法就是用它进行实验。

递归实例

将两个数字相加很容易，但将一系列数字相加则更为复杂。在以下示例中，递归用于将一系列数字相加，方法是将其分解为两个数字相加的简单任务：

public class MyClass {
  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);
  }
  public static int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);
    } else {
      return 0;
    }
  }
}

实例解析

调用sum()函数时，它将参数k添加到小于k的所有数字的和中，并返回结果。 当k变为0时，函数只返回0。运行时，程序遵循以下步骤：

由于函数在k为0时不调用自身，因此程序停止并返回结果。

停止状态

正如循环会遇到无限循环的问题一样，递归函数也会遇到无限递归的问题。 无限递归是指函数从不停止调用自身。每个递归函数都应该有一个停止条件，即函数停止调用自身的条件。 在前面的示例中，停止条件是当参数k变为0时。

看到各种不同的例子有助于更好地理解这个概念。在本例中，函数在起点和终点之间添加一系列数字。 此递归函数的停止条件为end不大于start时：

public class MyClass {
  public static void main(String[] args) {
    int result = sum(5, 10);
    System.out.println(result);
  }
  public static int sum(int start, int end) {
    if (end > start) {
      return end + sum(start, end - 1);
    } else {
      return end;
    }
  }
}