Java 递归指南

递归是一种编程样式，其中方法重复调用其自身，直到满足某个预定条件为止。 这种方法调用也称为递归方法。

1. 递归方法的语法

基于递归的方法必须具有两个基本组成部分才能正确解决问题。

1. 递归方法调用
2. 打破递归的前提

请记住，如果无法达到或未定义前提条件，则会发生栈溢出问题。

method(T parameters...) 
{
    if(precondition == true)      //precondition
    {
        return result;
    }

    return method(T parameters...);      //recursive call
}

2. 递归类型

根据何时进行递归方法调用，递归有两种类型。

1. 尾递归

当递归方法调用是该方法内部执行的最后一条语句时（通常与return语句一起使用），则递归方法为尾递归。

method(T parameters...) 
{
    if(precondition == true)      
    {
        return result;
    }

    return method(T parameters...);     
}

2. 头递归

不是尾递归的任何递归都可以称为头递归。

method(T parameters...) 
{
    if(some condition)      
    {
        return method(T parameters...);
    }

    return result;     
}

3. Java 递归示例

3.1 斐波那契序列

斐波那契数列是一个数字序列，其中每个数字都定义为两个数字之和。

例如 -1、1、2、3、5、8、13、21、34，依此类推…

此函数为我们提供从 1 开始的第 n 个位置的斐波那契数。

public int fibonacci(int n) 
{
    if (n <= 1) {
        return n;
    }
    return fibonacci(n-1) + fibonacci(n-2);
}

让我们测试一下此函数以打印n = 10的斐波那契数列；

public static void main(String[] args) 
{
  int number = 10;

  for (int i = 1; i <= number; i++) 
  {
    System.out.print(fibonacci(i) + " ");
  }

}

程序输出。

1 1 2 3 5 8 13 21 34 55 

3.2 最大公约数

两个正整数的最大公约数（gcd）是最大的整数，该整数平均分为两个整数。

public static int gcd(int p, int q) {
    if (q == 0) return p;
    else return gcd(q, p % q);
}

让我们测试一下此函数以打印n = 10的斐波那契数列：

public static void main(String[] args) 
{
  int number1 = 40;
  int number2 = 500;

  System.out.print( gcd(number1, number2) );
}

程序输出：

20

让我知道您有关 Java 中递归的问题。