1、Java 递归

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

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

递归就是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况。

2、递归示例

将两个数字加在一起很容易，但是将一系列数字相加则比较复杂。在下面的示例中，递归通过将其分解为添加两个数字的简单任务而用于将多个数字加在一起：

例如：

使用递归将所有数字加到10。

public class Main {
  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。当运行时，程序遵循以下步骤:

10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0

因为函数在k为0时不调用自身，所以程序在这里停止并返回结果。

3、递归跳出条件

就像循环会遇到无限循环的问题一样，递归函数也会遇到无限递归的问题。 无限递归是函数永不停止调用自己。 每个递归函数都应具有停止条件，即该函数停止自行调用的条件。 在前面的示例中，跳出条件是参数k变为0时。

看到各种不同的示例有助于更好地理解该概念。 在此示例中，该函数在开始和结束之间添加多个数字。 此递归函数的跳出条件是end不大于start时：

例如：

使用递归将5到10之间的所有数字相加。

public class Main {
  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;
    }
  }
}

4、递归的应用

1）计算阶乘

求一个数的阶乘是练习简单而典型的例子，阶乘的递推公式为：factorial(n)=n*factorial(n-1)，其中n为非负整数,且0!=1,1!=1

我们根据递推公式可以轻松的写出其递归函数：

public class Main {
  public static long factorial(int n){
    if (n < 0)
        System.out.println("参数不能为负！");
    else if (n == 1 || n == 0)
        return 1;
    else
        return n * factorial(n - 1);
    return 0;
  }
  public static void main(String[] args) {
    System.out.println(factorial(6));
  }

}

2）斐波那契数列

public class Main {
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0; // 基准条件
        }
        if (n == 1) {
            return 1; // 基准条件
        }
        return fibonacci(n - 1) + fibonacci(n - 2); // 递归步骤
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));
    }
}

3）反转字符串

递归地反转一个字符串。

public class Main {
    public static String reverse(String str) {
        // 基准条件：当字符串长度为 0 或 1 时，直接返回字符串
        if (str.isEmpty()) {
            return str;
        }
        // 递归步骤：取第一个字符后剩余部分反转
        return reverse(str.substring(1)) + str.charAt(0);
    }

    public static void main(String[] args) {
        String input = "hello";
        System.out.println("Reversed: " + reverse(input));
    }
}