数据结构与算法：递归算法
递归算法
什么是递归？
函数直接或间接调用自身的过程称为递归，相应的函数称为递归函数。使用递归算法，可以很容易地解决某些问题。此类问题的示例包括汉诺塔 (TOH)、中序/先序/后序树遍历、图的 DFS 递归函数通过调用自身的副本并解决原始问题的较小子问题来解决特定问题。需要时可以生成更多的递归调用。重要的是要知道我们应该提供某种情况来终止这个递归过程。
所以我们可以说，每次函数调用自身时都会使用原始问题的简单版本。
为什么需要递归
递归是一项令人惊奇的技术，借助它我们可以减少代码的长度并使其更易于阅读和编写。与稍后将讨论的迭代技术相比，它具有某些优点。对于可以用其相似的子任务来定义的任务，递归是最好的解决方案之一。例如：数字的阶乘。
递归的性质
- 使用不同的输入多次执行相同的操作。
- 在每一步中，我们都会尝试较小的输入来使问题更小。
- 需要基本条件来停止递归，否则会发生无限循环。
算法步骤
在函数中实现递归的算法步骤如下：
第1步： 定义基本情况：确定解决方案已知最简单情况。这是递归的停止条件，因为它防止函数无限地调用自身。
步骤2： 定义递归情况：用更小的子问题来定义问题。将问题分解为更小的子问题，并递归调用函数来解决每个子问题。
步骤3： 确保递归终止：确保递归函数最终到达基本情况，并且不会进入无限循环。
步骤4： 合并解决方案：合并子问题的解决方案来解决原问题。
数学解释
让我们考虑一个问题，程序员必须确定前 n 个自然数的和，有多种方法可以做到这一点，但最简单的方法是将从 1 到 n 的数字相加。所以这个函数看起来就像这样：
方法(1) ： 简单地一一相加
f(n) = 1 + 2 + 3 +……..+ n
另一种数学方法可以表示这一点:
方法(2) – 递归添加
f(n) = 1 n=1 f(n) = n + f(n-1) n>1
方法(1)和方法(2)之间有一个简单的区别，那就是在**方法(2)**中，函数“ f() ”本身在函数内部被调用，因此这种现象被称为递归，并且函数包含递归被称为递归函数，最后，这是程序员手中的一个很好的工具，可以以更简单有效的方式编写一些问题。
递归函数如何存储在内存中？
递归使用更多内存，因为递归函数会在每次递归调用时将值添加到堆栈中，并将值保留在那里，直到调用完成。递归函数使用 LIFO（后进先出）结构，就像堆栈数据结构一样。
递归的基本条件是什么？
在递归程序中，提供了基本情况的解决方案，并用较小的问题来表达较大问题的解决方案。
int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}在上面的示例中，定义了 n < = 1 的基本情况，并且可以通过将数字转换为较小的值来求解较大的值，直到达到基本情况。
如何使用递归解决特定问题？
这个想法是用一个或多个较小的问题来表示一个问题，并添加一个或多个停止递归的基本条件。例如，如果我们知道 (n-1) 的阶乘，我们就可以计算阶乘 n。阶乘的基本情况是 n = 0。当 n = 0 时，我们返回 1。
为什么递归会出现Stack Overflow错误？
如果未达到或未定义基本情况，则可能会出现堆栈溢出问题。让我们举个例子来理解这一点。
int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}如果调用fact(10)，它将调用fact(9)、fact(8)、fact(7)等，但数量永远不会达到100。因此，未达到基本情况。如果堆栈上的内存被这些函数耗尽，就会导致堆栈溢出错误。
直接递归和间接递归有什么区别？
如果函数 fun 调用相同的函数 fun，则该函数被称为直接递归。如果函数 fun 调用另一个函数（例如 fun_new ）并且 fun_new 直接或间接调用 fun ，则该函数被称为间接递归。直接递归和间接递归之间的区别如表 1 所示。
// 直接递归的示例
void directRecFun()
{
// Some code....
directRecFun();
// Some code...
}
// An example of indirect recursion
void indirectRecFun1()
{
// Some code...
indirectRecFun2();
// Some code...
}
void indirectRecFun2()
{
// Some code...
indirectRecFun1();
// Some code...
}递归中如何为不同的函数调用分配内存？
当从 main() 调用任何函数时，都会在堆栈上为其分配内存。递归函数调用自身，被调用函数的内存分配在分配给调用函数的内存之上，并且为每个函数调用创建不同的局部变量副本。当达到基本情况时，函数将其值返回给调用它的函数，并且内存被解除分配，并且该过程继续。 让我们通过一个简单的函数来举例说明递归是如何工作的。
PHP
<?php
// PHP程序演示 递归的工作原理
// 用于演示递归工作的函数
function printFun($test)
{
if ($test < 1) {
return;
} else {
echo("$test ");
printFun($test-1);
echo("$test ");
return;
}
}
$test = 3;
printFun($test);Javascript
<script>
// JavaScript程序演示递归的工作原理
function printFun(test)
{
if (test < 1) {
return;
} else {
console.log(test + " ");
printFun(test - 1); // statement 2
console.log(test + " ");
return;
}
}
// Driver code
let test = 3;
printFun(test);
</script>输出
3 2 1 1 2 3时间复杂度： O(1) 辅助空间： O(1)
当从 main() 调用printFun(3)时，内存被分配给 printFun(3)，局部变量 test 被初始化为 3，语句 1 到 4 被压入堆栈，如下图所示。它首先打印“3”。在语句 2 中，调用printFun(2)，为 **printFun(2)**分配内存，并将局部变量 test 初始化为 2，并将语句 1 到 4 压入堆栈。
类似地，printFun(2)调用printFun(1)，printFun(1)调用printFun(0)。printFun(0)转到 if 语句，然后返回到printFun(1)。**printFun(1)的其余语句被执行并返回到printFun(2)**等等。在输出中，打印从 3 到 1 的值，然后打印 1 到 3。内存堆栈如下图所示。
使用递归解决的实际问题并了解其基本工作原理
问题 1： 编写一个递归关系程序来查找 n 的斐波那契数列，其中 n>2 。
数学方程：
如果 n == 0，n == 1；输出：0, 1 否则: fib(n) = fib(n-1) + fib(n-2)
递归关系： T(n) = T(n-1) + T(n-2) + O(1)
递归程序：
输入： n = 5 输出： 斐波那契数列 5 个数字为：0 1 1 2 3
package main
import (
"fmt"
"testing"
)
func fib(n int) int {
if n == 0 {
return 0
} else if n == 1 || n == 2 {
return 1
}
return fib(n-1) + fib(n-2)
}
func Test_fib(t *testing.T) {
var n = 5
for i, _ := range make([]int, n) {
fmt.Println(fib(i))
}
}输出: 斐波那契数列 5 个数字是： 0 1 1 2 3
时间复杂度： O(2n ) 辅助空间： O(n)
这是输入 5 的递归树，它清楚地显示了如何将大问题解决为小问题。 fib(n) 是斐波那契函数。给定程序的时间复杂度取决于函数调用。
对于最好的情况: T(n) = θ(2^n\2)
**问题 2：**编写一个程序和递归关系来查找 n 的阶乘，其中 n>2 。
数学方程：
如果 n == 0 或 n == 1，则为 1； f(n) = n*f(n-1) 如果 n> 1；
递归关系：
T(n) = 1（n = 0） T(n) = 1 + T(n-1)（n > 0）
递归程序：输入： n = 5 输出： 5 的阶乘为：120
Golang
func f(n int) int {
if n == 0 {
return 0
}
if n == 1 {
return 1
}
return n * f(n-1)
}
func Test_t(t *testing.T) {
var n = 5
rest := f(n)
fmt.Println(rest)
}