什么是递归算法

什么是递归？
递归是函数直接或间接调用自身的操作，关联的函数称为递归函数。递归方法可以相对轻松地解决一些问题。汉诺塔（TOH）、顺序/前序/后序树遍历、图的 DFS 等都是这些问题的几个例子。通过调用自身的副本并解决原始问题的较小子问题，递归函数可以解决特定问题。当需要时，可以产生许多额外的递归调用。重要的是要理解，我们必须提出一个特定的情况来停止这个递归过程。因此，每次该函数都会将自己称为初始问题的简化版本。

递归算法使用较小的输入值调用自身，并对次要输入的返回值执行基本操作后，提供当前输入的结果。如果可以通过应用解决方案来解决同一问题的较小版本，并且较小版本减少为易于解决的示例，则递归方法可以解决问题。

您将把提供的问题陈述分成两部分来构建递归算法。主要情况是第一个，递归步骤是第二个。

基本情况：这是该问题最简单的解决方案，仅包含结束递归函数的条件。当满足特定条件时，在此基本情况下评估结果。
递归步骤：它通过重复调用同一函数但使用更次要或简单的输入来计算结果。
需要递归：
递归是一种奇妙的方法，它使我们能够缩短代码并简化理解和编写。与迭代方法相比，它提供了一些好处，稍后将介绍。递归是完成相关子任务可能描述的工作的最佳方法之一。例如，数字的阶乘。

递归的特点
递归的特点包括：

• 使用不同的输入重复相同的操作。
• 为了使每个阶段的问题变得更小，我们尝试使用更小的输入。
• 基本条件必须停止递归；否则，将导致无限循环。

算法的步骤
以下算法步骤用于在函数中实现递归：

• 步骤 1：建立主要案例。选择答案显而易见或微不足道的最直接的情况。这是递归的停止条件，它阻止函数无限期地调用自身。
• 在第二步中定义递归情况：用较小的对应项来描述问题。递归调用该函数将允许您通过将问题分解为更小的版本来解决每个子问题。
• 步骤 3：验证递归是否结束：确保递归代码不会进入无限循环并最终到达基本情况。
• 步骤 4：合并解决方案。要回答主要问题，请结合子问题的解决方案。

递归函数以什么方式存储在内存中？
递归会消耗额外的内存，因为递归函数每次调用都会添加到堆栈中，并将项目存储在那里，直到调用结束。与堆栈数据结构一样，递归函数也使用 LIFO（后进先出）结构。

递归基本前提条件是什么
递归适用的上下文前提条件是什么？基本情况的解决方案会在递归程序中给出，而更重要的问题的解决方案则以更小的问题的形式给出。

int fact(int n)  
{  
    if (n < = 1) //基本情况 前提条件
        return 1;  
    else      
        return n*fact(n-1);      
}  

前面提到的示例中描述了 n = 1 的基本前提，并且可以通过缩小数字直到达到基本条件来解决数字的更优异的值。

如何使用递归来解决特定问题？
这样做的目的是将更重要的问题分解成更次要的问题，然后添加一个或多个基本条件来停止递归。例如，如果我们知道 (n-1) 的阶乘，就可以计算 n 的阶乘。

为什么递归会导致堆栈溢出错误？
如果没有达到或定义基例，就可能出现堆栈溢出问题。为了进一步理解这个问题，我们来看一个例子。

int fact(int n)  
{  
    // 错误的基例（可能导致  
    // 堆栈溢出）；
    if (n == 100)   
        return 1;  
  
    else  
        return n*fact(n-1);  
}  

如果调用了 fact(10)，则还会调用 fact(9)、fact(8)、fact(7) 等，但总数始终是 100。主要情况仍需实现。如果堆栈上的这些函数占满了所有可用内存，就会发生堆栈溢出故障。

如何区分直接递归和间接递归？
如果一个函数调用了另一个名为 fun 的函数，那么这个函数就是直接递归函数。如果函数 fun 调用另一个函数（如 fun_new），而 fun_new 直接或间接地调用 fun，那么这个函数就被称为间接递归函数。表 1 举例说明了直接递归和间接递归的区别。

//直接递归示例  ；
void directRecFun()  
{  
    // Some code...  
  
    directRecFun();  
  
    // Some code...  
}  
  
// 间接递归示例  ；
void indirectRecFun1()  
{  
    // Some code...  
  
    indirectRecFun2();  
  
    // Some code...  
}  
void indirectRecFun2()  
{  
    // Some code...  
  
    indirectRecFun1();  
  
    // Some code...  
}  

如何区分有尾递归和无尾递归？
当递归调用是函数的最终动作时，就称为尾递归。更多信息，请参阅有关尾递归的文章。

递归如何将内存分配给各种函数调用？
从 main() 调用任何函数时，都会在堆栈中分配内存。每次递归函数调用自身时，都会复制一份新的局部变量，并在为调用函数分配的内存之上为被调用函数分配内存。当函数执行到基本情况时，内存被释放，进程继续，并将其值传递给调用它的函数。

让我们用一个简单的函数来演示递归的功能。

递归方法的内存分配
每次递归调用都会在新的堆栈内存副本中生成函数。一旦操作返回一些数据，副本就会从内存中删除。由于函数内部指定的所有参数和其他变量都保留在堆栈中，因此每次递归调用都会保留一个单独的堆栈。在返回适当函数的值后，堆栈将被移除。

关于解析和跟踪每次递归调用的值，递归是相当棘手的。因此，你必须跟踪栈的内容和变量的值。请查看下面的示例，进一步了解递归函数如何分配内存。

//斐波那契程序递归函数  
int Fib(int num)  
{  
   if ( num == 0 )  
      return 0;  
   else if ( num == 1 )  
      return 1;  
   else  
      return ( Fib(num-1) + Fib(num - 2) );  
}   
//假设我们要计算 n=5   的斐波纳契数；
Fib(5)  

现在来看看 n = 5 的递归斐波那契算法。在打印 n 的匹配值之前，首先保存所有堆栈，直到 n 等于零。一旦满足终止条件，将 0 返回到调用栈，然后逐个消除栈。

代码演示

// 演示递归工作的 C++ 程序；
#include <bits/stdc++.h>  
using namespace std;  
  
void printFun(int test)  
{  
    if (test < 1)  
        return;  
    else {  
        cout << test << " ";  
        printFun(test - 1); // statement 2  
        cout << test << " ";  
        return;  
    }  
}  
  
//主代码
int main()  
{  
    int test = 3;  
    printFun(test);  
}  

时间复杂性：O(1)

辅助空间O(1)

Java代码：
// 演示递归工作原理的 Java 程序

class GFG {  
    static void printFun(int test)  
    {  
        if (test < 1)  
            return;  
        else {  
            System.out.printf("%d ", test);  
            printFun(test - 1); // statement 2  
            System.out.printf("%d ", test);  
            return;  
        }  
    }  
  
    // Driver Code  
    public static void main(String[] args)  
    {  
        int test = 3;  
        printFun(test);  
    }  
}  

Python

# A Python 3 program to  
# demonstrate the working of  
# recursion  
  
  
def printFun(test):  
  
    if (test < 1):  
        return  
    else:  
  
        print(test, end=" ")  
        printFun(test-1) # statement 2  
        print(test, end=" ")  
        return  
  
# Driver Code  
test = 3  
printFun(test)  

上述代码从给定的正数打印到零（0），然后再从零（0）打印到给定的数字。

C#

// A C# program to demonstrate  
// working of recursion  
using System;  
  
class GFG {  
  
    // function to demonstrate  
    // working on recursion  
    static void printFun(int test)  
    {  
        if (test < 1)  
            return;  
        else {  
            Console.Write(test + " ");  
  
            // statement 2  
            printFun(test - 1);  
  
            Console.Write(test + " ");  
            return;  
        }  
    }  
  
    // Driver Code  
    public static void Main(String[] args)  
    {  
        int test = 3;  
        printFun(test);  
    }  
}  

PHP

<?php  
// PHP program to demonstrate  
// working of recursion  
  
// function to demonstrate  
// working of recursion  
function printFun($test)  
{  
    if ($test < 1)  
        return;  
    else  
    {  
        echo("$test ");  
          
        // statement 2  
        printFun($test-1);  
          
        echo("$test ");  
        return;  
    }  
}  
  
// Driver Code  
$test = 3;  
printFun($test);  
?>  

Javascript

<script>  
  
// JavaScript program to demonstrate the working of  
// recursion  
  
function printFun(test)  
    {  
        if (test < 1)  
            return;  
        else {  
            document.write(test + " ");  
            printFun(test - 1); // statement 2  
            document.write(test + " ");  
            return;  
        }  
    }  
  
// Driver code  
    let test = 3;  
    printFun(test);  
  
</script>  

• 当从 main() 调用打印 (3) 时，本地变量 test 被初始化为 3，语句 1 至 4 被放入堆栈。首先打印 "3"。
• 语句 2 调用 printFun(2)，为 printFun(2) 分配内存，将局部变量 test 初始化为 2，并将语句 1 至 4 推入堆栈。
• printFun(0) 调用 printFun(1)，printFun(1) 以类似的方式调用 printFun(2)。
• 在 if 语句之后，printFun(0) 返回 printFun(1)。
• 完成 printFun(1) 的剩余语句后，它将转到 printFun(2)，
• 依此类推。输出中首先写入 3 到 1 的值，然后写入 1 到 3 的值。

总结
递归是一种功能强大的方法，在编程和计算机科学中有多种用途。以下是递归的几种典型用途：

• 树和图遍历：在搜索和遍历树和图等数据结构时，递归被广泛使用。递归算法可用于系统地研究树或图的每个节点或顶点。
• 排序算法：快速排序和合并排序等排序算法也采用递归算法。在这些技术中，数据被分割成更小的子数组或子列表，进行排序，然后使用递归进行合并。
• 分而治之算法：许多算法，如二进制搜索算法，都采用了分而治之的策略，利用递归将更重要的问题分成更小的子问题。
• 分形生成：递归算法可产生分形形式和模式。例如，曼德布罗特集就是在递归算法中不断应用复数而产生的。
• 回溯算法 回溯算法用于解决涉及一系列决定的问题，而每个决定都取决于之前的决定。递归可用于创建这些算法，以检查每一条途径，并在找不到解决方案时进行回溯。
• 记忆：这种策略包括缓存昂贵函数调用的结果，并在再次提供相同输入时返回这些结果。递归函数可用于计算和存储子问题的结果，以实现记忆。

这些只是编程和计算机科学递归法众多用途中的一小部分。递归是一种灵活有效的方法，可以解决各种问题。

解释：下面是一个递归的实际例子：

编程递归使用了函数调用自身的思想。它可以有效地解决具有挑战性的问题，但必须精心设计，以防止无限循环和堆栈溢出。

递归编程和迭代编程之间存在哪些缺点？
请注意，每个递归程序都可以迭代地构造，反之亦然。这意味着递归程序和迭代程序都具有相同的解决问题的能力。由于所有函数都将保留在堆栈中，直到达到基本情况，因此递归程序比迭代程序需要更多的存储空间。由于函数调用和返回开销，它也需要更多时间。

此外，由于代码较短，因此更难掌握，因此在创建代码时需要更加小心。如果递归调用没有得到充分验证，机器可能会耗尽内存。

与迭代编程相比，递归编程技术有什么好处？
递归提供了一种简洁明了的代码构建技术。有些问题，比如树遍历、汉诺塔等，本质上是递归的。建议使用递归编码来解决此类问题。此类程序也可以使用堆栈数据结构重复创建。河内迭代塔和无递归的中序树遍历就是例子。

递归有两种情况：递归情况和基本情况。

• 当情况有效时，基本情况结束递归函数。
• 每次递归调用时，该方法都会在堆栈内存上复制。
• 如果使用无限递归，堆栈内存最终可能会耗尽。
• 归并排序、快速排序、汉诺塔、斐波那契数列、阶乘问题等都是递归算法的一些例子。