4

可能重复：
递归函数示例

我一直在尝试将编程中的递归作为一个概念来研究（尽管我专门研究 Java），这是我最好理解的：

例如，在现实生活中，递归就是我们将两个镜子放在彼此的前面，并且它们之间产生的图像是递归的。

但是我在编程中没有得到这个算法？有人可以给我一个简化的例子来理解递归吗？

4

6 回答 6

19

递归是一种编程技术，其中方法可以调用自身作为其计算的一部分（有时您可以拥有多个方法 - 然后这些方法通常会循环调用彼此）。

一个流行的例子是计算斐波那契数：

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

两个基本组件是基本案例（n<=1在示例中）和递归案例。

在创建递归算法时，您需要考虑基本情况以及如何使用递归情况来达到基本情况（否则最终会出现无限递归并破坏堆栈）。

于 2012-11-30T13:50:19.407 回答
6

基本上，一个函数是递归的

  1. 一个函数有一个简单的基本情况，当
  2. 所有其他情况都有减少到基本情况的规则。

例如，计算阶乘：

public static long factorial(int i)
{
    // This is the base case
    if(i == 0)
    {
         return 1;
    }
    else
    {
        // This reduces the problem to something closer to the base case
        return i * factorial(i - 1);
    }
}
于 2012-11-30T13:54:46.573 回答
3

一些计算问题可以这样描述，即问题可以分解为更小的子问题。使用与主要问题相同的方法解决较小的子问题。如果较小的子问题只是较大问题的较小情况，那么它本身可以进一步分解。

最终，问题是如此之小，以至于无需进一步分解即可解决。这被称为基本情况。通过基本案例的解决方案，您可以构建更大问题的解决方案。

假设您想找到 a b其中 a 和 b 是正整数。您可以看到这与 a * a (b-1)相同。也就是说，a (b-1)是比原始问题更小的问题，但仍需要与原始问题相同的技术来解决。要解决 a (b-1)你会看到它是 a * a (b-2)。

等等。

最终你会得到 a * a * a * ... * a (bb)。我们知道 bb = 0 和 a 0 = 1。所以我们不必计算最后一点，因为我们已经知道答案。最终，a b = a * a * a * ... * 1。

所以 2 4 = 2 * 2 3 = 2 * 2 * 2 2 = 2 * 2 * 2 * 2 1 = 2 * 2 * 2 * 2 * 2 0 = 2 * 2 * 2 * 2 * 1。

要编写此程序，您首先要处理基本情况，然后使用递归来处理其他所有情况。

   pow(a, b){
       if(b == 0){
          return 1;
       }else{

          return a * pow(a, b - 1);
       }
   }

需要注意的是，这只是递归的基本思想。您在诸如斐波那契数问题的各种答案中看到的这些示例非常低效。您可以使用动态编程技术构建更高效的程序，该技术使用递归作为解决问题的机制之一。

于 2012-11-30T14:07:03.317 回答
2

递归编程是一种基于数学归纳思想的技术，其中方法或函数重复调用自身。因此，可以按如下方式实现阶乘函数：

int fact(int n) {
    if (n < 2) {
            return 1;
    }

    return n * fact(n-1);
}

请注意，为了确保递归终止，您应该确保处理基本情况，即您为一些已知的简单输入定义了常量输出，并且您应该确保在每次迭代时使函数的参数更简单（在上面的例子中减少n1)。

于 2012-11-30T13:57:05.057 回答
1

非常简单的“递归”代码。

处理列表的顶部项目。从列表中删除它并调用代码来处理列表的顶部项目。

树根有一定的长度，每2/3根就分裂成单独的根。分裂的部分每 2/3 个根分裂成单独的根。分裂片的分裂片分裂每个..等等。

于 2012-11-30T13:51:57.167 回答
1

递归

一个方法可以调用自己，这就是递归。经常使用方法的递归实现，因为它们会产生紧凑优雅的代码，这比不使用递归的对应实现更容易理解。

递归编程技术知道三个重要的规则（经验法则）：

  1. 基本情况：递归有基本情况。总是第一个语句是有条件的并且有一个'return'。
  2. 子问题：递归调用解决在某种意义上更小的子问题，使其收敛到基本情况。
  3. 无重叠：递归调用不应处理重叠的子问题。

从性能的角度来看，非递归解决方案更快，并且通常需要更少的内存。（例如二分搜索）
但是有些任务非常复杂，只有递归解决方案才能产生（或多或少可理解的）代码。

递归二分查找示例：

public static int binSearch(int[] a, int key) {
   return binSearch0(a, key, 0, a.length - 1);
}

public static int binSearch0(int[] a, int key, int from, int to) {
    if (from > to) return -1;
    // looks strange but (from + to) / 2 can oveflow
    // (java bug which was active more than 10 years)
    int mid = from + (to - from) / 2;
    if (key < a[mid]) 
        return binSearch0(a, key, from, mid - 1);
    else if (key < a[mid]) 
        return binSearch0(a, key, mid + 1, to);
    else return mid;
 }

在该示例中，您会看到所有三个规则（base、sub、non oberlap）。
并不是说递归函数通常有一个启动函数，例如示例中的“binSearch”。其中 'binSearch0' 是递归函数。

于 2012-11-30T14:37:03.997 回答