通过基础数论理解 Java 中的递归
4.74/5 (10投票s)
在本文中，我们将了解如何在 Java 程序中使用递归。
引言
我们知道，方法是一个命名可执行指令块，可以从程序的多个位置调用。通常，它们有两种类型：迭代和递归。
迭代方法在其主体中包含循环结构，并被程序员频繁使用。另一方面，递归方法更复杂，使用它们需要更多的工作。
在本文中，我们将通过基础数论介绍递归背后的背景概念。所以，如果你准备好看到Java-数学的友好关系，那就开始吧！
背景
递归是一种技术，可以为使用简单循环难以编程的问题提供优雅的解决方案。
这意味着在适当的情况下强烈建议使用递归方法，因此您应该熟悉这些技术，以提升您在 Java 编程中的经验。
必备组件
Java
递归
除了调用其他方法外，方法也可以调用自身。这称为递归。如果你问我“为什么递归在 Java 中有效？”，我会告诉你因为它在数学中有效。事实上，递归与数学中一个著名的主题——归纳法相关。
在接下来的部分中，我将介绍这个想法背后的数学原理。目前，递归的定义对我们来说就足够了。更多细节将在示例中展示。
数学
数学归纳法
数学归纳法是一种数学证明方法，通常用于证明给定语句适用于所有自然数。它是一种直接证明形式，分为两步完成。
简单地说，它的意思是如果命题 P 对于 1 为真，并且我们可以得出结论，如果 n 满足 P，那么 n+1 也满足 P；那么所有自然数都满足 P。参见 https://en.wikipedia.org/wiki/Mathematical_induction。
自然数
自然数是正整数。所有自然数的集合用N表示。所以 1、2、545 是自然数，但 0、-6 和 12.5 不是。参见 https://en.wikipedia.org/wiki/Natural_number。
整数
整数是自然数、0 或自然数的负数。所有整数的集合用I（或有时用Z，德语“zahlen”意为数字）表示。所以 1、-9 和 0 是整数，但 0.5、-6.7 和 Pi 不是。参见 https://en.wikipedia.org/wiki/Integer。
除法算法
设 m 和 n 为两个任意整数。如果存在一个整数 q 使得 n = m*q，则称 m 整除 n 或 n 是 m 的倍数。在这种情况下，q 称为商，m 称为除数，n 称为被除数。有一个基本定理称为除法算法，它指出对于任意正整数 m 和 n，m 不等于 0，存在唯一一对整数，即 r 和 s，使得 n = m*q + r，其中 r
G.C.D.：最大公约数
设 m 和 n 为两个整数，且不同时为 0。如果 d 同时整除 m 和 n，则称 d 是 m 和 n 的公约数。很容易证明，对于我们的 m 和 n，存在一个最大公约数，称为最大公约数（G.C.D.）。
我们使用 gcd(m,n) 来表示 m 和 n 的最大公约数。它有许多性质，但这里使用其中一个，即 如果 m 大于或等于 n，则 gcd(m,n) = gcd(m-n,n)。参见 https://en.wikipedia.org/wiki/Greatest_common_divisor。
阶乘函数
设 n 为一个自然数。1*2*3*...*n-2*n-1*n 记作 n! 并读作“n 的阶乘”。所以阶乘只是乘法，尽管它们在数论中扮演着非常重要的角色，尤其是在组合学中。我们需要这个重要的等式：n! = n * (n-1)!。参见 https://en.wikipedia.org/wiki/Factorial。
斐波那契数列
序列就是一串数字。例如，1、2、3、... 是自然数序列。序列中的每一项都由一个称为索引的数值决定。所以我们示例序列中的 2 具有索引 2，因为它是序列中的第二项。
斐波那契数列是一个特殊的数列，其形式如下：1, 1, 2, 3, 5, 8, 13, ...
它有许多有趣的性质。其中之一是它的定义，它是以递归方式进行的：序列的第 n 项是前两项的和。参见 https://en.wikipedia.org/wiki/Fibonacci_number。
Using the Code
现在我们准备好处理递归了。为了演示概念，我们开发了一个名为 Recursion 的类，用于计算乘法、阶乘、斐波那契数列、最大公约数等等。Recursion 类同时包含迭代和递归方法，因此我们可以轻松地比较它们。
理论已经足够了。让我们开始编码吧。
package Main;
/**
* @作者 MrSH http:www.thevelop.ir
*/
/** This class has static methods to describe Recursion in Java */
public class Recursion {
/** finds x*y in an iterative fashion
* @param x first number
* @param y second number
* @return returns the production of two numbers using iterative approach
*/
public static long iterativeMultiplication(long x, long y){
long production = 0;
for (int i = 0; i < y; i++)
production+=x;
return production;
}
/** finds x*y in a recursive fashion
* @param x first number
* @param y second number
* @return returns the production of two numbers using recursive approach
*/
public static long recursiveMultiplication(long x, long y){
if(y == 1)
return x;
return x + recursiveMultiplication(x, y-1);
}
/** finds n! in an iterative fashion
* @param n input for factorial calculation
* @return returns n! using iterative approach
*/
public static long iterativeFactorial(long n){
long factorial = 1;
for (int i = 1; i <= n ; i++) {
factorial *= i;
}
return factorial;
}
/** finds n! in a recursive fashion
* @param n input for factorial calculation
* @return returns n! using recursive approach
*/
public static long recursiveFactorial(long n){
if (n==1 || n== 0)
return n;
return n * recursiveFactorial(n-1);
}
/** finds nth term of Fibonacci sequence in an iterative fashion
* @param n input for calculation
* @return returns nth term of Fibonacci sequence using iterative approach
*/
public static long iterativeFibonacci(long n){
long x=1, y=1, z=1;
for (int i = 3; i <= n; i++) {
z=x+y;
x=y;
y=z;
}
return z;
}
/** finds nth term of Fibonacci sequence in a recursive fashion
* @param n input for calculation
* @return returns nth term of Fibonacci sequence using recursive approach
*/
public static long recursiveFibonacci(long n){
if (n==1 || n==2)
return 1;
return recursiveFibonacci(n-1)+recursiveFibonacci(n-2);
}
/** finds G.C.D(x,y) in an iterative fashion
* @param x first input
* @param y second input
* @return returns G.C.D(x,y) using iterative approach
*/
public static long iterativeGCD(long x, long y){
long GCD = 1;
long minimum = Math.min(x, y);
for (int i = 1; i <= minimum; i++) {
if (x%i == 0 && y%i == 0) {
GCD = i;
}
}
return GCD;
}
/** finds G.C.D(x,y) in a recursive fashion
* @param x first input
* @param y second input
* @return returns G.C.D(x,y) using recursive approach
*/
public static long recursiveGCD(long x, long y){
if(x==1 || y == 1)
return 1;
if (x==0)
return y;
if(y==0)
return x;
if (x>=y)
return recursiveGCD(y, x-y);
return recursiveGCD(x, y-x);
}
}
代码分析
iterativeMultiplication：它是如何工作的？
从上学时起我们就知道 x * y 意味着 x * ( 1 + 1 + 1 + ... + 1 )，其中括号中有 y 个 1；我们也知道 x * ( 1 + 1 + 1 + ... + 1 ) = x + x + x + ... + x。所以在我们的 for 循环中，我们将 x 自身相加 y 次以得到 x * y。
如您所见，此方法背后的思想非常简单、直接和基础。
recursiveMultiplication：它是如何工作的？
从高中时代 :) 我们记得 x * y = x * ( 1 + y - 1 )，所以 x * y = x + x * ( y - 1 )，并且记住 1 是乘法的单位元，这意味着 x * 1 = x。虽然我认为这个说明已经足够了，但让我们更详细地研究这个方法，因为递归是本文的主题。
考虑以下代码片段
public static void main(String[] args) {
System.out.println(Recursion.recursiveMultiplication(5, 3));
}
执行过程如下
!( 3 == 1 ) => return 5 + recursiveMultiplication(5, 2);
!( 2 == 1 ) => return 5 + [ 5 + recursiveMultiplication(5, 1); ]
( 1 == 1 ) => return 5 + [ 5 + [ 5 ] ] == 15
System.out.println(15);
iterativeFactorial：它是如何工作的？
如前所述，n! = 1 * 2 * 3 * ... * n。所以在 for 循环中，我们声明一个阶乘变量，初始化为 1。然后将其乘以 1、2、...、n 以获得 n!。不再赘述！
recursiveFactorial：它是如何工作的？
利用关系 n! = n * ( n -1 )!，我们每一步都减少 n，直到达到 1。在数学中，0! 定义为 1，显然 1! = 1。
考虑以下代码片段
public static void main(String[] args) {
System.out.println(Recursion.recursiveFactorial(6));
}
!( 6 ==1 ) => return 6 * recursiveFactorial(5);
!( 5 ==1 ) => return 6 * [ 5 * recursiveFactorial(4); ]
!( 4 ==1 ) => return 6 * [ 5 * [ 4 * recursiveFactorial(3); ] ]
!( 3 ==1 ) => return 6 * [ 5 * [ 4 * [ 3 * recursiveFactorial(2); ] ] ]
!( 2 ==1 ) => return 6 * [ 5 * [ 4 * [ 3 * [ 2 * recursiveFactorial(1); ] ] ] ]
( 1 ==1 ) => return 6 * [ 5 * [ 4 * [ 3 * [ 2 * 1 ] ] ] ] == 720
System.out.println(720);
iterativeFibonacci：它是如何工作的？
根据斐波那契数列的定义，此方法的实现非常简单。
recursiveFibonacci：它是如何工作的？
为了说明这一点，例如，考虑 recursiveFibonacci(4)；请看下图以理解评估过程。
iterativeGCD：它是如何工作的？
在此方法中，我们首先将 GCD 设置为 1。由于我们知道当 m 整除 n 时，m 小于或等于 n，因此我们获取输入的最小值。在 for 循环中，我们从 1 数到最小值，当我们找到更大的除数时，我们将 GCD 更改为该值。
recursiveGCD：它是如何工作的？
在这种情况下，我们只使用最大公约数的性质，例如 gcd(m,n) = gcd(n,m)，gcd(m,1) = 1，gcd(m,0) = m，以及我们之前提到的关系：如果 m 大于或等于 n，则 gcd(m,n) = gcd(m-n,n)。
例如，考虑以下代码片段
public static void main(String[] args) {
System.out.println(Recursion.recursiveGCD(24, 12));
}
( 24 >= 12 ) => return recursiveGCD(12,12);
( 12 >= 12 ) => return recursiveGCD(12,0);
( 0 == 0 ) => return 12;
System.out.println(12);
延伸阅读
我鼓励你搜索以下主题以扩展你的知识，从而递归地思考:)
- Java 中的汉诺塔递归算法
- Java 中使用递归反转数字
- Java 中使用递归选择排序
- Java 中使用递归二分查找
- Java 中使用递归生成分形