Python 函数：Python 中的递归

一种更直接的方法是将学校分成几个部分，直到可以制作最小的部分来找到学生，也就是说，首先搜索她所在的年级，然后是班级会更有意义，然后您将能够更容易地找到她的位置。尽管由于 return 语句中存在函数名称，调用似乎是尾递归的，但这并不是因为在这种情况下调用是表达式的一部分。如果在递归函数中，其中的所有调用都是尾递归的，则称为尾递归。在尾递归函数中，函数完成的最后一个任务是递归调用，因此在递归调用发生

新华

2344人浏览 · 2024-01-31 06:00:00

新华 · 2024-01-31 06:00:00 发布

概述

递归是计算机科学中使用的一种计算问题解决技术，其中解决方案依赖于同一问题的较小实例的解决方案。它使用从其代码中调用自己的函数来解决此类递归问题。该战略适用于广泛的问题。

什么是 Python 中的递归？

如果我们放置两面平行的镜子会发生什么？您将看到由表面之间的反射引起的多个图像被拉伸到无穷大。

想象一下，你想知道你所站的队列中一个人的名字。你要求人们去了解它。

他们不停地问下一个人，直到找到答案。一旦找到答案，他们就会将其发回，直到它到达您手中。

上面的两个例子描述了一个过程，在这个过程中，一个特定的动作被重复，直到满足一个条件。这些过程与我们所说的递归非常相似。

函数调用自身的过程称为递归。此过程通过将迭代代码替换为递归语句来帮助简化解决问题的方法。

在 Python 中处理递归

想象一下，坐在礼堂里，对你所坐的那一排感到困惑。由于你不能数到第一张长凳，所以你问你前面的人他们坐在哪一排。如果这个人不知道他的座位号，他会问他前面的人。

询问过程将继续进行，直到有人知道他们的座位号。如上图所示，当第 3 排的人通知他坐在第 3 排时，他后面的人会加一个，并立即将他的第 4 排传给后面的人。行号将在每行中计算，并将传递到您手中。到达您手中后，将 1 加起来即可获得最后一行号。

这正是 Python 中递归的工作原理。

在 Python 中使用递归

很多时候，人们想知道为什么我们应该在循环存在的情况下使用递归。一切都可以在没有递归的情况下进行编码。

迭代和递归之间的区别在于递归代码没有顺序结束。它在基本条件下进行测试，只要满足该条件，就可以继续进行。

递归在 Python 中使用，当问题可以分解为更简单的部分，以便于计算和更易读的代码时。

例如，如果您想搜索学校的学生，则有两种方法可以做到这一点。你可以把所有的学生聚集在一个礼堂里，然后一个接一个地寻找她。一种更直接的方法是将学校分成几个部分，直到可以制作最小的部分来找到学生，也就是说，首先搜索她所在的年级，然后是班级会更有意义，然后您将能够更容易地找到她的位置。

尽管在某些情况下，如果优化得当，递归可以更快地给出结果，但它也会增加内存使用量。

因此，应仅在需要时使用递归。

Python 中的递归函数

在 Python 或任何其他编程语言中，递归是函数调用自身的过程。此类函数称为递归函数。

在上面给出的礼堂示例中，我们将有一个名为 divide_and_search（）的递归函数，它接受一组学生。根据某个部分中学生的存在与否，递归函数将在每次调用该函数时再次运行，从而缩短学生之间的间隔。

这意味着，当第一次调用递归函数时，礼堂中所有参与者的位置，我们将检查学生是否在礼堂的特定一侧。

如果学生在左边，只有奇数年级的学生坐在那里，我们现在将奇数年级的学生传递给递归函数。在下一次调用时，将在奇数年级内搜索学生，以找到她所在的特定年级。

此过程将持续到找到所需的学生为止。

Python 中的递归函数分为两部分：

（a） 基本情况 - 这有助于我们终止递归函数。这是一个可以直接回答并且不使用递归的简单情况。如果满意，它将返回最终的可计算答案。如果省略这一点，该函数将运行到无穷大。

Python 解释器通过给出递归错误将函数的递归调用次数限制为 1000 次。

（b） 一般（递归）情况 - 此情况使用递归，除非满足基本条件，否则将调用该情况。

语法：

def rec_func_name():
   if(condition)                       # base case
       simple statement without recursion
   else                                # general case
       statement calling rec_func_name()

必须首先确定基本情况及其解决方案才能编写递归函数。根据具体情况，可以使用多个基本情况。一旦确定了基本情况，就必须确定一般情况或递归情况，以便每次递归调用都使我们离实现基本情况更近一步。

递归函数使用调用堆栈。每次调用递归函数时，该函数都会添加到此堆栈的顶部。想象一下，打开一个洋葱，你把你剥的每一层都放在它附近。因此，每一层去皮后，都会被放置在这个去皮堆栈的顶部。

现在将其与递归函数进行比较。剥离每一层将是一个递归函数调用。当第一层被剥离时，第一个 peel（）将添加到堆栈的顶部，然后下一个将添加到其上方，依此类推，直到该过程完成。

递归函数示例

假设你想在 python 中找到 n 个自然数的总和。我们将编写以下代码来获得答案。

def sum(n):
    if n <= 1:   # base case
        return n
    else:        # general or recursive case
        ans = sum(n - 1)
    return n + ans


print(sum(6))

输出：

加工：当我们用任何正整数（比如 6）调用函数 sum（）时，它将通过递减数字来递归调用自己。如递归情况所示，每个函数调用都会将 number 参数与递减数字之和的值相加，如下所示：

sum(6)=6+sum(5) =6+5+sum(4) =6+5+4+sum(3)
=6+5+4+3+sum(2)
=6+5+4+3+2+sum(1)
=6+5+4+3+2+1
=21

让我们通过下面的分步流程图更好地理解这一点。递归过程在调用 sum（6）时开始，在我们进入基本情况时结束，即当 sum （1）返回 1 时。返回此值后，将其添加到调用堆栈中的所有值中，如下所示，最后返回值 21。

所有递归函数都有两个不同的工作阶段 - 卷绕阶段和展开阶段。绕组阶段从第一次调用递归函数开始，并向前移动，直到最后一次递归调用。在此阶段，不执行任何 return 语句。当调用中基本情况的条件变为真时，绕组阶段终止。

这时，展开阶段就开始了。在此阶段，所有递归函数都以相反的顺序返回，直到函数的第一个实例返回。

Python 中的递归类型

递归函数主要有两种类型：

直接递归
间接递归

1）直接递归

在这种类型的递归中，函数调用自身。

a）尾递归 - 如果递归调用是函数内部执行的最后一个语句，则称其为尾递归调用。

尾部递归调用示例

以下函数按降序打印 n 中的自然数。它是通过将数字从 n 遍历到 1 并在调用时返回每个数字来完成的。在此示例中，打印语句的位置具有最重要的意义。基本情况为 0，其中不会向调用返回任何值。

在函数的第一次调用中，print 语句会导致 5 显示在屏幕上，并在堆栈的顶部添加 disp（4）。在下一次调用中，打印 4，并将 disp（5）添加到堆栈中。

同样，3、2 和 1 在以下调用中打印。在最后一次调用中，n 的值变为 0，因此满足基本情况，导致递归终止。

def dispn(n):
    if n == 0:
        return  # Base case
    print(n)
    dispn(n - 1)  # Tail Recursive Call


dispn(5)

输出：

非尾递归调用的示例

以下函数用于按升序打印最多 n 的自然数。与前面的示例相比，print 语句发生在此函数中的递归调用之后。因此，打印语句仅在展开阶段起作用。

在函数的连续调用中，disp（5）、disp （4）、disp（3）、disp（2）、disp （1）分别添加到堆栈的顶部。当我们遇到 disp（0）时，终止条件得到满足，返回函数。此时，展开阶段开始。调用以相反的顺序返回，disp（1）首先返回，其余调用紧随其后。

因此，disp（1）的 print 语句出现在之前。因此，这些值按升序打印。

def dispn(n):
    if n == 0:
        return  # Base case
    dispn(n - 1)  # Not a Tail Recursive Call
    print(n)


dispn(5)

输出：

在非 void 函数中，如果递归调用出现在 return 语句中并且不是表达式的一部分，则该调用是尾递归的。

尾递归调用示例

以下函数用于计算 2 个给定数字的 GCD。众所周知，如果较小的数字为 0，那么两个数字的 GCD 将是较大的数字。这是我们问题的基本情况。

通过欧几里得余数算法，我们知道：

GCD(a,b)=GCD(b,a/b)

考虑 a=49 和 b=35，然后

GCD(49,35)=GCD(35,14)
=GCD(14,7)
=GCD(7,0)
=7

代码如下：

def GCD(a, b):
    if b == 0:
        return a  # Base case
    return GCD(b, a % b)  # Tail Recursive Call


print(GCD(49, 35))

输出：

非尾递归调用的示例

以下函数用于计算给定数字的阶乘。尽管由于 return 语句中存在函数名称，调用似乎是尾递归的，但这并不是因为在这种情况下调用是表达式的一部分。在此示例中，基本情况是当数字为 0 时，返回值 1。

阶乘的一般公式是-

n!=n∗n−1∗n−2∗…..∗1

因此，在每次递归调用时，当前 n 将乘以前一个数字的阶乘。

def fact(n):
    if n == 0:
        return 1  # Base case
    return (n * fact(n - 1))  # Not a tail-recursive call


print(fact(5))

输出：

如果在递归函数中，其中的所有调用都是尾递归的，则称为尾递归。在尾递归函数中，函数完成的最后一个任务是递归调用，因此在递归调用发生后没有挂起的操作。考虑以下函数，它以相反的顺序显示前 5 个自然数。

def tailr(n):
    if n > 0:
        print(n, end=" ")
        tailr(n - 1)


p = 5
tailr(p)

输出：

5 4 3 2 1

b）磁头递归

如果在递归函数中，最后一条语句不是递归调用，即在展开阶段，还有一些步骤要发生，那么就称为头递归。

考虑以下函数，该函数按升序显示前五个自然数。在函数的连续调用中，headr（5）、headr（4）、headr（3）、headr（2）、headr（1）分别添加到堆栈的顶部。当我们遇到 headr（0）时，满足终止条件，返回函数。

此时，展开阶段开始。调用以相反的顺序返回，headr（1）首先返回，其余调用紧随其后。因此，headr（1）的 print 语句发生在之前。因此，这些值按升序打印。

def headr(n):
    if n > 0:
        headr(n - 1)
        print(n, end=" ")


p = 5
headr(5)

输出：

1 2 3 4 5

2. 间接递归

在这种类型的递归中，该函数调用另一个函数，该函数调用原始函数。在这里，当调用函数 A（）时，它首先执行 print 语句，然后调用函数 B（），增量值为 n。它的 print 语句在函数 B 中执行，然后调用值为 n 减去 5 的函数 A（）。

只要不满足终止条件，该过程就会继续。

def A(n):
    if n > 0:
        print("", n, end='')
        B(n + 1)


def B(n):
    if n > 1:
        print("", n, end='')
        A(n - 5)


A(20)

输出：

20 21 16 17 12 13 8 9 4 5

间接递归中的函数链可能涉及任意数量的函数。我们可以让 f1（）调用 f2（）调用 f3（）调用 f4（）调用 f5（）又调用 f1（）。间接递归的使用增加了代码的复杂性，因此不是很常见。

Python 中的递归与数字

递归非常常用于计算数字的运算。一些最常见的示例是查找数字的阶乘、显示或计算一系列数字的总和、反转整数以及测试可除性。

让我们看一些例子来更详细地理解这一点。

1. 能被 7 整除

根据 7 的可整除规则，如果一个数字的单位数字的两倍与余数之间的差是 7 或 0 的倍数，则整数可以被 7 整除。

假设一个数字的格式为 10a+b，其中 b 是单位数字，a 是数字/10。

如果 10a+b 能被 7 整除，则 2 （10a+b）可被 7 整除，然后 20 A + 2B 可被 7 整除 21a - a + 2b 可被 7 整除

消除 21 的倍数，我们有 A - 2B 可被 7 整除。因此，10a-2b 能被 7 整除，当且仅当（a-2b）能被 7 整除。

考虑数字 798。
a=79，b=8 => a-2b=79-16= 63，可被 7 整除。因此，798 也可以被 7 整除。

我们用于此问题的递归函数将有 2 个递归案例和 2 个基本案例。如果给我们的数字是负数，我们将首先将其转换为正数，然后调用递归函数。

这是通过否定给我们的负数来完成的。满足 7 的可除性检验的最小值是 0 和 7。因此，我们函数的终止条件是测试数字是 0 还是 7。如果满足终止条件，则基本情况返回 True。现在，如果这两个条件都不满足并且数字小于 10，则表示该数字不能被 7 整除。

因此，在这种情况下，该函数返回 False。在给定的例子中，如果 a-2b 能被 7 整除，则一个数字可以被 7 整除。这里，a = num/10 和 b = num - num/10 * 10。因此，为了检查数字是否能被 7 整除，我们在每次调用时调用 a-2b 的递归函数，以便执行递归调用：num/10 = 2* （num=num/10 *10）

代码：

def isDivisibleBy7(num):
    if num < 0:
        return isDivisibleBy7(-num)
    if num == 0 or num == 7:
        return True
    if num < 10:
        return False
    return isDivisibleBy7(num // 10 - 2 * (num - num // 10 * 10))

print(isDivisibleBy7(63))
print(isDivisibleBy7(70))

输出：

False
True

2. 数字的阶乘

阶乘是所有小于或等于给定数字的数字的乘积。
例如，阶乘5=5∗4∗3∗2∗1=120在此示例中，基本情况是当数字为 0 时，值 1 返回。阶乘的一般公式如下：

n!=n∗n−1! =n∗n−1∗n−2∗…..∗1

因此，在每次递归调用时，当前 n 将乘以前一个数字的阶乘。因此，5 的阶乘计算如下：

fact(5)=5∗fact(4)
=5∗4∗fact(3)
=5∗4∗3∗fact(2)
=5∗4∗3∗2∗fact(1)
=5∗4∗3∗2∗1
=120

下面的图表可以更好地理解上述工作：

代码：

def fact(n):
    if n == 1:
        return n
    else:
        return n * fact(n - 1)


print(fact(5))

输出：

3. 求斐波那契数列中的第 n 个数

斐波那契数列是从 0,1 开始的数列，其中数字可以计算为前两个数字的总和。10 位斐波那契数列如下：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

求第 n 个斐波那契数列的问题可以递归定义为：

基本情况：

当 n=0 时，返回的值将为 0
当 n=1 或 n=2 时，返回的值将为 1

递归案例：.

使用递归调用找到前 2 个数字的总和，由下式给出：

fib(n−1)+fib(n−2)

代码：

def fib(n):
    if n == 0:
        return 0  # Base Case
    elif n == 1 or n == 2:
        return 1  # Base Case
    return (fib(n - 1) + fib(n - 2))  # Recursive Case 


print(fib(8))

输出：

4. 整数反转

我们从右到左读取所有数字以反转整数，即从单位位置向后。
例如，765 的反面是 567。

算法：

将名为 res 的变量初始化为 0。
如果给定整数大于 0 一个。将 res*10+剩余数字添加到 res。 b.将数字除以 10

如果我们必须找到 524 的反面，我们可以按以下步骤进行：

代码：

res = 0
start = 1


def reverseDigits(num):
    global res
    global start
    if num > 0:
        reverseDigits(int(num / 10))
        res += (num % 10) * start
        start *= 10
    return res


print(reverseDigits(524))

输出：

Python 中使用字符串和数组的递归

Python 中的字符串可以递归定义为：

空字符串。
字符后跟一个比原始字符串小 1 个字符的字符串。

同样，Python 中的数组可以递归定义为：

空数组。
数组元素后跟一个比原始数组小 1 个数组元素的数组。

这些是我们在解决字符串和数组递归问题时要考虑的主要原则。

字符串和数组的递归广泛用于排序、反转、计算满足给定条件的元素数以及计算序列。

以下是一些示例，可帮助您更好地了解如何在 Python 中的数组和字符串中使用递归。

1. 升序与否

假设你得到一个随机排序的整数数组。系统要求您检查数组是否按升序排列，即递增，最小数字放在前面，其他数字放在后面。为了实现这个问题的解决方案，给定一个字符串，我们首先要计算给定数组的长度。正如在数组的递归定义中所讨论的，我们考虑 2 种情况：

基本情况 -
a。长度为 0 的数组 - 空数组（无需排序）
b.长度为 1 的数组 - 只有一个元素的数组（已排序）

在这两种情况下，我们不需要对数组进行进一步排序，从而返回 True 值。

递归案例 -当我们的数组有多个元素时，就会触发这种情况。因此，我们比较每次调用递归调用时的元素对，并递归调用下一次调用，如下所示：

arr[0] <= arr [1] 和 isAscending（arr[1：]）

因此，在第一次调用时，将比较位置 0 和 1 处的元素，并返回 this 的 AND 值以及数组中下一个元素的比较。

在展开阶段结束时，仅当整个数组按升序排列时，才会返回 True 值。让我们考虑一个数组：1、2、3、4 5。操作如下：

1 < = 2 并且是升序（2,3,4,5）
True 和 2<=3 并且是升序（3,4,5）
True 和 True 和 3<=4 和 isAscending（4,5）
True 和 True 和 4 <= 5 True
True

代码：

def isAscending(arr):
   n = len(arr)
   if n == 1 or n == 0:
       return True
   return arr[0] <= arr[1] and isAscending(arr[1:])
 
arr=[1,4,2,3,5]
print(isAscending(arr))
 
arr=[1,2,3,4,5]
print(isAscending(arr))

输出：

False
True

2. 元音数量

给定一个字符串，我们必须计算其中存在的元音数量。为此，我们将使用两个函数：isVowel（）来检查所考虑的字符是否是元音和 countVowels（），一个递归函数，用于计算字符串中存在的元音数量。当调用 countVowels 函数时，我们传递字符串及其长度。

如前所述，考虑到字符串的递归定义，可以包含元音的最小字符串长度为一个字符。如果字符串长度为一个字符，我们通过调用 isVowel（）函数来检查它是否是元音。

在比较中，先将字符转换为大写，然后再进行比较，以减少同一元音的不同大小写之间的比较次数。对于具有多个字符的字符串，我们检查最后一个字符是否为元音，如果是元音，则在消除最后一个字符后将字符串传递给 countVowels（）函数，从而将字符串添加到返回的值中。

假设我们得到了字符串“Eat”。第一次调用后，我们会将 countVowels 应用于字符串 'Ea'。由于“t”不是元音，因此元音的数量目前为 0。

在第二次调用之后，我们将 countVowels（）应用于字符串 'E'。由于“a”是元音，因此元音的数量现在将增加到 1。

在第三次调用之后，我们为 E 调用 isVowel（）函数。由于“E”是元音，因此元音的数量现在将更改为 2。现在返回最后一个值 2。

代码：

def isVowel(ch):
    return ch.upper() in ['A', 'E', 'I', 'O', 'U']


def countVowels(str, n):
    if n == 1:
        return isVowel(str[n - 1])

    return countVowels(str, n - 1) + isVowel(str[n - 1])


str = "Hello World!"
print(countVowels(str, len(str)))

输出：

3. 回文

回文是一个单词或数字/字符序列，其向后读取方式与向前读取方式相同。

回文的例子是 12321 和马拉雅拉姆语。正如字符串的递归定义中所讨论的，我们考虑 2 种情况：

基本情况 -长度为 1 的字符串 - 只有一个字符的字符串。它是一个回文，因此，我们返回一个 True 值。
递归案例 -当我们的字符串有多个字符时，就会触发此功能。
因此，我们在每次调用递归调用时比较字符串两个极端的字符对，并以递归方式调用下一个调用，如下所示：
str[0] == str[-1]和isPalindrome（arr[1： -1]）

这里，str[-1] 表示字符串中的最后一个字符。因此，在第一次调用时，将比较位置 0 和 n-1（其中 n= 字符串的长度）处的字符。并返回 this 的 AND 值以及字符串的以下字符的比较。

在展开阶段结束时，仅当所有比较都返回 True 时，才会返回 True 值。

考虑字符串“ABA”。操作如下：

A == A 和 isPalindrome（str[1：-1]）
真实与真实
真

代码：

def isPalindrome(str):
    if len(str) <= 1:
        return True
    else:
        return str[0] == str[-1] and isPalindrome(str[1:-1])


print(isPalindrome('ABCBA'))
print(isPalindrome('ABCA'))

输出：

True
False

4. 字符串的反转

给定一个字符串，我们需要将其反转，即从右到左（从头到尾）打印字符串。我们考虑 2 种情况来解决这个问题：

基本情况：如果字符串为空，即其长度为 0，则我们从函数返回。
递归情况：这种情况一直执行，直到字符串有字符。在这里，我们将字符串的第一个字符分配给一个临时变量，并为字符串的其余部分调用 strRev（）函数。

一旦字符串为空，展开阶段就开始了。它从打印字符串中的最后一个字符开始，然后向后移动，直到所有字符都打印在屏幕上。因此，最终输出包含相反顺序的字符串。

假设要反转的字符串是“Hello”。然后，收卷和放卷阶段将按如下方式进行：

代码：

def strRev(str):
    if len(str) == 0:
        return
    temp = str[0]
    strRev(str[1:])
    print(temp, end='')


print(strRev('Hannah'))

输出：

hannaHNone

Python 中的数据结构递归

使用数据结构可以更有效地存储和组织 Python 中的数据。根据所服务的目的使用各种结构。这些数据结构决定了可以对数据执行的操作。

我们可以在 Python 中以递归方式定义数据结构本身。它帮助我们利用递归结构;因此，它们可以使用递归函数自然地实现。这种类型的递归称为结构递归。让我们看两个例子来了解如何在 Python 中为链表和树实现递归。

1. 在末尾插入节点并使用递归遍历链表

在 Python 中，可以使用链接（以指针的形式）连接数据序列以节省内存。与数组不同，链表仅为要存储的值分配内存，从而避免了任何内存浪费。

Python 中的链表递归定义为：

空链表。
一个节点，后跟一个比原始链表小一个节点的链表。

要在链表的末尾插入节点，我们需要遍历链表，直到最后一个元素（即元素的链接）为空值（None）。下面的示例演示用于插入和遍历链表的递归函数。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


def newNode(data):
    new_node = Node(data)
    new_node.data = data
    new_node.next = None
    return new_node


def insertEnd(head, data):
    if (head == None):
        return newNode(data)
    else:
        head.next = insertEnd(head.next, data)
    return head


def traverse(head):
    if (head == None):
        return
    print(head.data, end=" ")
    traverse(head.next)


head = None
head = insertEnd(head, 6)
head = insertEnd(head, 8)
head = insertEnd(head, 10)
head = insertEnd(head, 12)
head = insertEnd(head, 14)
traverse(head)

输出：

6 8 10 12 14

在上面的代码中，首先定义了一个节点类。它包含节点保存的数据和指向下一个元素的链接。最初，下一个元素被视为 None。

在第一次分配期间，节点类的对象将使用数据的值进行实例化。由于第一个节点也是当时链表的最后一个节点，因此下一个节点的值为 None。

要在链表末尾插入新节点，请执行以下操作：

基本情况：如果链表是空的，或者我们已经到达了最后一个节点，即，如果对象的值是 None，则通过调用 NewNode（）函数来分配一个新节点。
一般情况：如果链表不为空，则调用 insertEnd（）函数。

要遍历链表，请执行以下操作：

基本情况：如果列表为空，即，如果对象具有 None 值，则返回 main。
一般情况：打印当前节点中的数据。然后为当前节点的链接调用 traverse（）函数。

2. 二叉树的无序遍历

一棵二叉树最多可以有 2 个子树，左边的和右边的分别称为左边的子树和右边的子树。

Python 中的二叉树是一组有限的节点，可以递归定义为：

一棵空树。
由称为 root 的可分辨节点组成的树，其余节点被划分为两个不相交的集合，都是二叉树。

与线性数据结构不同，我们可以以不同的方式遍历二叉树。Binaryal 的无序遍历返回左子节点（及其整个子树），然后是父节点，然后是右子节点（及其整个子树）。我们通常使用递归来遍历二叉树，因为它们是使用堆栈实现的。

代码：

class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


def inorder(root):
    if root is None:
        return
    # Traverse the left subtree
    inorder(root.left)
    # Display the current node
    print(root.data, end=' ')
    # Traverse the right subtree
    inorder(root.right)


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.right.left = Node(5)
root.right.right = Node(6)
root.right.left.left = Node(7)
root.right.left.right = Node(8)
inorder(root)