Python 中的递归

先决知识： Python 中的函数

你可能已经知道“递归”这个词的意思了。根据谷歌的解释，它指的是“一个过程或定义的重复应用”。在编程中也是如此，并且应用于函数。

任何在其主体中反复调用自身，直到某个特定条件变为假且目标任务完成的函数，都称为“递归函数”，这个过程称为“递归”。

本文讨论了我们如何使用 Python 函数来实现递归。

为了简单回顾一下函数，我们举个例子

输出

num is an even number

理解

在这里，evenORodd 是我们定义的用于检查给定数字 num 是偶数还是奇数的函数。我们定义了函数，然后在其中编写了逻辑。现在，我们想检查 2 是偶数还是奇数，所以我们通过将参数 2 传递给函数来调用该函数，该参数将替换 num，函数将继续执行。

什么时候需要递归调用函数？

当我们想要执行一项复杂的任务时，我们通常将其分解为更小的任务；一项接一项地完成它们可以减轻负担和复杂性。就像这样，当我们想为复杂问题编写代码时，我们会将其分解为更小且重复的部分。

举个简单的例子

我们需要编写一个程序来查找数字的阶乘。假设用户输入了 6

6! = 6 * 5 * 4 * 3 * 2 * 1

如果我们将其分解

6! = 6 * 5!

5! = 5 * 4!

4! = 4 * 3!

3! = 3 * 2!

2! = 2 * 1!

1! = 1

你可以注意到重复性。

将其公式化

N! = N * (N - 1)!

所以，我们编写一个函数，例如 N 的阶乘，在其中再次调用 N-1 的相同函数，直到 N=1 重复。

递归还是迭代

循环用于执行重复性任务，函数也是如此？有什么区别，以及如何知道何时使用哪个？

很简单。当我们使用循环时，我们需要知道需要迭代循环多少次，就像在 for 循环中一样。当知道迭代次数时，我们就使用 for 循环。否则，我们将只剩下 while 和 do-while 循环或递归。我们需要根据需要进行选择，在某些情况下，我们使用递归来获取返回值。

深入递归

语法

让我们以之前的代码——求数字的阶乘——为例。

输出

Enter a number: 5
The factorial of the given number is 120

理解

斐波那契数列

前两个数字是 0 和 1。我们将前两个数字相加得到下一个数字，这个数字序列称为斐波那契数列。

输出

The Fibonacci series up to 10 terms:
0
1
1
2
3
5
8
13
21
34

理解

我们需要打印斐波那契数列的前 10 个数字。

根据程序中的循环

fib (0) = 0

fib (1) = 1

fib (2) = fib (1) + fib (0) = 1 + 0 = 1

fib (3) = fib (2) + fib (1) = 1 + 1 = 2

fib (4) = fib (3) + fib (2) = 2 + 1 = 3

fib (5) = fib (4) + fib (3) = 3 + 2 = 5

fib (6) = fib (5) + fib (4) = 5 + 3 = 8

fib (7) = fib (6) + fib (5) = 8 + 5 = 13

fib (8) = fib (7) + fib (6) = 13 + 8 = 21

fib (9) = fib (8) + fib (7) = 21 + 13 = 34

fib (10) = fib (9) + fib (8) = 34 + 21 = 55

我们需要 10 个数字。所以，只包含从 0 到 9。

输出

32

理解

假设，对于相同的示例输入 - pwr(2, 6)

2 * 2 * 2 * 2 * 2 * 2

分解它

pow(2,6) = 2 * pow(2, 5)

pow(2,5) = 2 * pow(2, 4)

pow(2,4) = 2 * pow(2,3)

pow(2,3) = 2 * pow(2,2)

pow(2,2) = 2 * pow(2,1)

pow(2, 1) = 2

因此，我们调用 pwr(num, power) 函数，然后再次调用 pwr(num, power-1) 函数，直到 power 变为 1，此时 pwr(num, 1) = num 本身。

尾部递归

如果函数执行的最后一个任务是执行递归调用，则任何递归函数都称为尾递归函数。在尾部递归中，函数只返回一个对自身的调用——仅此而已。

普通递归和尾部递归的区别

让我们举个例子

这里有一个计算前“num”个自然数之和的代码。

这里发生的是

sum (5)

5 + sum (4)

5 + (4 + sum (3))

5 + (4 + (3 + sum (2)))

5 + (4 + (3 + (2 + sum (1))))

5 + (4 + (3 + (2 + (1 + sum (0)))))

5 + (4 + (3 + (2 + (1 + 0))))

5 + (4 + (3 + (2 + 1)))

5 + (4 + (3 + 3))

5 + (4 + 6)

5 + 10

15

解释器必须记住所有变量的值和调用直到程序结束。它需要记住 num 的值，以便在递归函数调用时继续乘以它。

现在，看看这段代码

这里的机制

sum(5, 0)

sum(4, 5)

sum(3, 9)

sum(2, 12)

sum(1, 14)

sum(0, 15)

15

解释器不必记住任何函数调用之外的变量值。它可以直接忽略它们，而专注于递归函数调用。如您所见，它只返回一个函数调用，仅此而已。

这很重要，因为

这些类型的函数（尾递归函数）可以被编译器优化并高效使用。另一方面，非尾递归函数无法被编译器优化。

当我们执行递归代码时，编译器通常会使用堆栈来存储每次递归调用时的参数值等。在遇到递归调用时，它会将所有新值推入堆栈。这个过程一直持续到函数结束。然后，所有值都会被弹出。

在非尾递归函数中，堆栈深度会更大，因为它包含更多需要编译器记住的值。在尾部递归的情况下，它不需要保留当前函数调用的堆栈帧。堆栈将其弹出。

如上面的自然数示例所示，我们将非尾递归函数转换为尾递归函数，以寻求编译器的优化。

这是转换后的阶乘函数。

你可能会认为这看起来像一个尾递归函数。但事实并非如此。在 return 语句中，函数调用有一个额外的乘以 num 的操作。我们在 return 语句中只需要函数调用本身。

这是给定的数字的阶乘转换后的尾递归代码。

递归的优点和缺点

递归在解决数据结构和堆栈演变问题方面非常有用。但同时，如果调用检查不当，将会浪费大量内存，计算机甚至可能耗尽内存。

递归既有优点也有缺点，它根据问题的需要使用，并且是 Python 编程中一种相当重要且有用的机制。