[已解决]python尾递归

huxxx

请问这样算是尾递归吗？

最佳答案

月排行榜 / 总排行榜

isdkz

2023-4-2 00:16:53

huxxx 发表于 2023-4-2 00:05
谢谢大佬的指导，那我还有个问题，就是如果我这里10行的return整个直接删除的话，那这个函数算是尾递归吗 ...

即使你删除第10行的 return li，这个函数仍然不能被认为是尾递归的。

这是因为在递归调用 glob(i, name, li) 之后，函数没有直接返回该递归调用的结果。

实际上，在递归调用之后，仍然会继续执行for循环（当 i.is_dir() 不为 True 的情况下）。

为了让你更好地理解，我将解释一下尾递归的概念。尾递归是指一个函数的递归调用发生在它的最后一步，

并且在递归调用之后没有任何其他操作。这使得编译器或解释器可以对递归过程进行优化，避免堆栈溢出。

在尾递归中，递归调用的返回值不需要与任何其他值相结合，也不需要进行任何操作。

在你的示例中，glob 函数的递归调用并不是在最后一步进行的，而且递归调用之后仍然需要执行循环。因此，这个函数不是尾递归的。

如果你希望将此函数转换为尾递归形式，可以尝试将其重构为一个内部函数，该内部函数接受一个额外的参数，如下所示：

from pathlib import Path

def glob(pa: Path, name: str):
    def _glob(pa: Path, name: str, li: list):
        for i in pa.iterdir():
            if i.is_file() and i.suffix == name:
                li.append(i.name)
            elif i.is_dir():
                li = _glob(i, name, li)
        return li

    return _glob(pa, name, [])

print(glob(Path.cwd(), ".txt"))

在这个修改后的版本中，我们将逻辑放在了一个名为 _glob 的内部函数中。

这个内部函数接受一个名为 li 的额外参数，这样我们就可以在每次递归调用中将其传递给下一层。

这使得递归调用成为函数的最后一步操作，从而满足尾递归的条件。

尽管这个版本看起来更接近尾递归，但需要注意的是，Python 并不会自动优化尾递归。

因此，这种改进在 Python 中并没有实质性的性能提升。在实际应用中，使用迭代方法通常是更好的选择，因为它不会导致堆栈溢出，并且性能更加可靠。

迭代的例子：

from pathlib import Path
from collections import deque

def glob(pa: Path, name: str):
    li = []
    q = deque([pa])

    while q:
        current_dir = q.popleft()

        for i in current_dir.iterdir():
            if i.is_file() and i.suffix == name:
                li.append(i.name)
            elif i.is_dir():
                q.append(i)

    return li

print(glob(Path.cwd(), ".txt"))

跳转到最佳答案楼层

isdkz

这里的递归调用不是函数里面的最后一个操作，所以不算是尾递归

歌者文明清理员

这个代码是有问题的，默认参数是可变量会导致程序结果错误。
你可以自行百度

不二如是

属于“尾递归”

在 Python 中，递归是一种异常耗费内存的操作，因为每次递归调用都会产生一个新的函数栈。

在某些情况下，可以使用尾递归（Tail Recursion）来优化代码，减少栈空间的使用。

尾递归是指：函数的最后一步是调用自身或者其他函数，且这个调用是整个函数的返回值。

在尾递归中，系统不需要保留任何关于当前函数的信息，而是直接将其替换成一个新的函数，这样就可以减少栈空间的使用。

下面是一个例子，计算斐波那契数列的第 $n$ 项：

def fib(n, a=0, b=1):
    if n == 0:
        return a
    elif n == 1:
        return b
    else:
        return fib(n-1, b, a+b)

print(fib(5))   # 输出 5

在这个例子中，`fib` 函数是一个尾递归函数，它的最后一步是调用 `fib(n-1, b, a+b)`。
在每次调用时，更新了变量 `a` 和 `b` 的值，然后将参数 `n-1` 传递给下一次函数调用，这样就可以实现递归的效果。同时，由于这是一个尾递归，所以不会出现栈空间不足的问题。

huxxx

歌者文明清理员 发表于 2023-3-31 16:40
这个代码是有问题的，默认参数是可变量会导致程序结果错误。
你可以自行百度

感谢大佬的指正，谢谢

huxxx

isdkz 发表于 2023-3-31 14:46
这里的递归调用不是函数里面的最后一个操作，所以不算是尾递归

谢谢大佬的指导，那我还有个问题，就是如果我这里10行的return整个直接删除的话，那这个函数算是尾递归吗？

huxxx

因为我对尾递归的理解就是一个函数执行的最后依次指令是再调用一次自己并把相应数据传入，不知道这样子的理解对不对？

isdkz

huxxx 发表于 2023-4-2 00:05
谢谢大佬的指导，那我还有个问题，就是如果我这里10行的return整个直接删除的话，那这个函数算是尾递归吗 ...

即使你删除第10行的 return li，这个函数仍然不能被认为是尾递归的。

这是因为在递归调用 glob(i, name, li) 之后，函数没有直接返回该递归调用的结果。

实际上，在递归调用之后，仍然会继续执行for循环（当 i.is_dir() 不为 True 的情况下）。

为了让你更好地理解，我将解释一下尾递归的概念。尾递归是指一个函数的递归调用发生在它的最后一步，

并且在递归调用之后没有任何其他操作。这使得编译器或解释器可以对递归过程进行优化，避免堆栈溢出。

在尾递归中，递归调用的返回值不需要与任何其他值相结合，也不需要进行任何操作。

在你的示例中，glob 函数的递归调用并不是在最后一步进行的，而且递归调用之后仍然需要执行循环。因此，这个函数不是尾递归的。

如果你希望将此函数转换为尾递归形式，可以尝试将其重构为一个内部函数，该内部函数接受一个额外的参数，如下所示：

from pathlib import Path

def glob(pa: Path, name: str):
    def _glob(pa: Path, name: str, li: list):
        for i in pa.iterdir():
            if i.is_file() and i.suffix == name:
                li.append(i.name)
            elif i.is_dir():
                li = _glob(i, name, li)
        return li

    return _glob(pa, name, [])

print(glob(Path.cwd(), ".txt"))

在这个修改后的版本中，我们将逻辑放在了一个名为 _glob 的内部函数中。

这个内部函数接受一个名为 li 的额外参数，这样我们就可以在每次递归调用中将其传递给下一层。

这使得递归调用成为函数的最后一步操作，从而满足尾递归的条件。

尽管这个版本看起来更接近尾递归，但需要注意的是，Python 并不会自动优化尾递归。

因此，这种改进在 Python 中并没有实质性的性能提升。在实际应用中，使用迭代方法通常是更好的选择，因为它不会导致堆栈溢出，并且性能更加可靠。

迭代的例子：

from pathlib import Path
from collections import deque

def glob(pa: Path, name: str):
    li = []
    q = deque([pa])

    while q:
        current_dir = q.popleft()

        for i in current_dir.iterdir():
            if i.is_file() and i.suffix == name:
                li.append(i.name)
            elif i.is_dir():
                q.append(i)

    return li

print(glob(Path.cwd(), ".txt"))

match123_xbd