java - 递归澄清

Question

我只是想确保我对递归完全了解。我已经在很多应用程序中使用过它，但意识到当有人要求我定义它时(一个新程序员问这个)，我对这个定义有点动摇，并且在解释它时遇到了一些麻烦。我只是想接触一个大型编程社区，以确保我走在正确的道路上。

据我所知，计算机科学中的递归是指给定问题或检查(即 if 语句)的某些答案取决于与同一方法相关的其他内容。解决这个问题的一种方法可能是调用自身的函数(大多数编程语言都支持)。我在下面编写了一个简单的斐波那契程序:

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

让我知道我是否走在正确的道路上。另外，我知道关于递归也有类似的问题，但请不要将此问题作为重复项关闭，因为这是一个更普遍的问题，不限于特定语言，而是更多关于什么是递归的概念。

谢谢

brd

Answer 1

你走在正确的道路上。我会把它分成几部分:

1. 定义:根据字典的定义，递归是一个调用自身的过程。此调用通常是直接的，如您的示例所示，但也可以是间接的:f1 和 f2 相互调用，但不调用自身。
2. 示例:正如您所做的那样...展示一个具有易于理解的递归定义的众所周知的函数。我通常使用阶乘，因为它只有一次递归调用；然后我介绍斐波那契案例。
3. 机制:描述基本情况的关键属性(最终停止的原因)和简化(在问题再次发生之前减少问题)。
4. 正确使用:几乎任何具有递归描述的实际编程应用程序都会有一个迭代(循环)解决方案，该解决方案需要更少的计算时间。但是，如果自然描述是递归的，那么从长远来看，最高效解决方案很可能是递归的。除了执行周期之外，还要考虑维修和维护资源，并记住 FLOPS 每个月都会变得更便宜。