1. Introduction

1.介绍

In this article, we’ll focus on a core concept in any programming language – recursion.

在这篇文章中，我们将重点讨论任何编程语言中的一个核心概念–递归。

We’ll explain the characteristics of a recursive function and show how to use recursion for solving various problems in Java.

我们将解释递归函数的特点，并展示如何使用递归来解决Java中的各种问题。

2. Understand Recursion

2.了解递归

2.1. The Definition

2.1.定义

In Java, the function-call mechanism supports the possibility of having a method call itself. This functionality is known as recursion.

在Java中，函数调用机制支持让方法调用自己的可能性。这种功能被称为递归。

For example, suppose we want to sum the integers from 0 to some value n:

例如，假设我们想对从0到某个值n的整数求和。

public int sum(int n) {
    if (n >= 1) {
        return sum(n - 1) + n;
    }
    return n;
}

There are two main requirements of a recursive function:

递归函数有两个主要要求。

A Stop Condition – the function returns a value when a certain condition is satisfied, without a further recursive call
The Recursive Call – the function calls itself with an input which is a step closer to the stop condition

Each recursive call will add a new frame to the stack memory of the JVM. So, if we don’t pay attention to how deep our recursive call can dive, an out of memory exception may occur.

每一次递归调用都会在JVM的堆栈内存中增加一个新的框架。因此，如果我们不注意我们的递归调用可以潜入多深，可能会发生内存不足的异常。

This potential problem can be averted by leveraging tail-recursion optimization.

这个潜在的问题可以通过利用尾部递归优化来避免。

2.2. Tail Recursion Versus Head Recursion

2.2.尾部递归与头部递归的比较

We refer to a recursive function as tail-recursion when the recursive call is the last thing that function executes. Otherwise, it’s known as head-recursion.

我们把递归函数称为tail-recursion 当递归调用是该函数执行的最后一件事时。否则，它被称为head-recursion。

Our implementation above of the sum() function is an example of head recursion and can be changed to tail recursion:

我们上面的sum()函数的实现是一个头递归的例子，可以改成尾递归。

public int tailSum(int currentSum, int n) {
    if (n <= 1) {
        return currentSum + n;
    }
    return tailSum(currentSum + n, n - 1);
}

With tail recursion, the recursive call is the last thing the method does, so there is nothing left to execute within the current function.

在尾部递归中，递归调用是方法所做的最后一件事，因此在当前函数中没有任何东西可以执行。

Thus, logically there is no need to store current function’s stack frame.

因此，从逻辑上讲，没有必要存储当前函数的堆栈框架。

Although the compiler can utilize this point to optimize memory, it should be noted that the Java compiler doesn’t optimize for tail-recursion for now.

尽管编译器可以利用这一点来优化内存，但需要注意的是，Java编译器暂时没有为尾部递归进行优化。

2.3. Recursion Versus Iteration

2.3.递归与迭代

Recursion can help to simplify the implementation of some complicated problems by making the code clearer and more readable.

递归可以帮助简化一些复杂问题的实现，使代码更清晰、更易读。

But as we’ve already seen the recursive approach often requires more memory as the stack memory required increases with each recursive call.

但正如我们已经看到的，递归方法往往需要更多的内存，因为每次递归调用所需的堆栈内存都会增加。

As an alternative, if we can solve a problem with recursion, we can also solve it by iteration.

作为一种选择，如果我们可以用递归来解决一个问题，我们也可以用迭代来解决它。

For example, our sum method could be implemented using iteration:

例如，我们的sum方法可以用迭代来实现。

public int iterativeSum(int n) {
    int sum = 0;
    if(n < 0) {
        return -1;
    }
    for(int i=0; i<=n; i++) {
        sum += i;
    }
    return sum;
}

In comparison to recursion, the iterative approach could potentially give better performance. That being said, iteration will be more complicated and harder to understand compared to recursion, for example: traversing a binary tree.

与递归相比，迭代方法有可能带来更好的性能。也就是说，与递归相比，迭代会更复杂，更难理解，例如：遍历二叉树。

Making the right choice between head recursion, tail recursion and an iterative approach all depend on the specific problem and situation.

在头部递归、尾部递归和迭代方法之间做出正确的选择，都取决于具体问题和情况。

3. Examples

3.例子

Now, let’s try to resolve some problems in a recursive way.

现在，让我们尝试以递归的方式解决一些问题。

3.1. Finding N-Th Power of Ten

3.1.寻找10的N次方

Suppose we need to calculate the n-th power of 10. Here our input is n. Thinking in a recursive way, we can calculate (n-1)-th power of 10 first, and multiply the result by 10.

假设我们需要计算10的n次幂。这里我们的输入是n.以递归的方式思考，我们可以先计算(n-1)-10的幂，然后将结果乘以10。

Then, to calculate the (n-1)-th power of 10 will be the (n-2)-th power of 10 and multiply that result by 10, and so on. We’ll continue like this until we get to a point where we need to calculate the (n-n)-th power of 10, which is 1.

然后，要计算10的(n-1)次方，将是10的(n-2)次方，并将这个结果乘以10，以此类推。我们将继续这样做，直到我们需要计算10的(n-n)次方，也就是1。

If we wanted to implement this in Java, we’d write:

如果我们想在Java中实现这一点，我们会写。

public int powerOf10(int n) {
    if (n == 0) {
        return 1;
    }
    return powerOf10(n-1) * 10;
}

3.2. Finding N-Th Element of Fibonacci Sequence

3.2.寻找斐波那契数列的N-Th元素

Starting with 0 and 1, the Fibonacci Sequence is a sequence of numbers where each number is defined as the sum of the two numbers proceeding it: 0 1 1 2 3 5 8 13 21 34 55 …

从0和1开始，斐波那契数列是一个数列，每个数字都被定义为前面两个数字之和。0 1 1 2 3 5 8 13 21 34 55 …

So, given a number n, our problem is to find the n-th element of Fibonacci Sequence. To implement a recursive solution, we need to figure out the Stop Condition and the Recursive Call.

所以，给定一个数字n，我们的问题是找到n斐波那契数列的第3个元素。为了实现一个递归的解决方案，我们需要弄清楚停止条件和递归调用。

Luckily, it’s really straightforward.

幸运的是，这真的很简单。

Let’s call f(n) the n-th value of the sequence. Then we’ll have f(n) = f(n-1) + f(n-2) (the Recursive Call).

让我们称f(n)为序列的n-th值。然后我们将得到f(n) = f(n-1) + f(n-2)（递归调用）。

Meanwhile, f(0) = 0 and f(1) = 1 ( Stop Condition).

同时，f(0)=0，f(1)=1（停止条件）。

Then, it’s really obvious for us to define a recursive method to solve the problem:

那么，对我们来说，定义一个递归方法来解决这个问题真的很明显。

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

3.3. Converting from Decimal to Binary

3.3.从十进制到二进制的转换

Now, let’s consider the problem of converting a decimal number to binary. The requirement is to implement a method which receives a positive integer value n and returns a binary String representation.

现在，让我们考虑将一个十进制数字转换为二进制的问题。要求是实现一个接收正整数值n并返回二进制String表示的方法。

One approach to converting a decimal number to binary is to divide the value by 2, record the remainder and continue to divide the quotient by 2.

将十进制数字转换为二进制的一种方法是用数值除以2，记录余数，然后继续将商除以2。

We keep dividing like that until we get a quotient of 0. Then, by writing out all of the remainders in reserve order, we obtain the binary string.

我们一直这样除下去，直到我们得到一个0的商。然后，通过按保留顺序写出所有的余数，我们得到二进制字符串。

Hence, our problem is to write a method that returns these remainders in reserve order:

因此，我们的问题是写一个方法，按保留顺序返回这些余数。

public String toBinary(int n) {
    if (n <= 1 ) {
        return String.valueOf(n);
    }
    return toBinary(n / 2) + String.valueOf(n % 2);
}

3.4. Height of a Binary Tree

3.4.二叉树的高度

The height of a binary tree is defined as the number of edges from the root to the deepest leaf. Our problem now is to calculate this value for a given binary tree.

二叉树的高度被定义为从根到最深的叶子的边的数量。我们现在的问题是为一个给定的二叉树计算这个值。

One simple approach would be to find the deepest leaf then counting the edges between the root and that leaf.

一个简单的方法是找到最深的叶子，然后计算根和该叶子之间的边。

But trying to think of a recursive solution, we can restate the definition for the height of a binary tree as the max height of the root’s left branch and the root’s right branch, plus 1.

但是，为了思考一个递归的解决方案，我们可以把二叉树的高度定义重述为根的左分支和根的右分支的最大高度，加上1。

If the root has no left branch and right branch, its height is zero.

如果根没有左分支和右分支，其高度为零。

Here is our implementation:

以下是我们的实现。

public int calculateTreeHeight(BinaryNode root){
    if (root!= null) {
        if (root.getLeft() != null || root.getRight() != null) {
            return 1 + 
              max(calculateTreeHeight(root.left), 
                calculateTreeHeight(root.right));
        }
    }
    return 0;
}

Hence, we see that some problems can be solved with recursion in a really simple way.

因此，我们看到，有些问题可以用递归的方式来解决，非常简单。

4. Conclusion

4.结论

In this tutorial, we have introduced the concept of recursion in Java and demonstrated it with a few simple examples.

在本教程中，我们介绍了Java中递归的概念，并通过几个简单的例子进行了演示。

The implementation of this article can be found over on Github.

这篇文章的实现可以在Github上找到over。