How to use Python to understand recursion (code explanation)

The content of this article is about how to use Python to understand recursion (code explanation). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Recursion

When a function is called one or more times during execution, it is itself recursive, just like a Russian matryoshka doll. Contains another doll.

Recursion is actually something that you will come into contact with very quickly in the process of learning programming languages. However, there may be some omissions in the understanding of recursion. Let’s have a more in-depth understanding of this aspect

Classification of recursion

Here are divided into linear recursion, two-way recursion and multiple recursion according to the number of recursive calls

Linear recursion

If a recursive call starts at most one other recursive call, we call it linear recursion.

For example:

def binary_search(data, target, low, high):
    """
    二分查找，对有序列表进行查找，如果找到则返回True，否则返回False 
    """

    if low > high:
        return False
    else:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            return binary_search(data, target, low, mid - 1)
        else:
            return binary_search(data, target, mid + 1, high)

Although there are two binary_searches in the code, they are executed under different conditions and can only be executed once each time, so it is linear recursion.

Two-way recursion

If one recursive call can start two other recursive calls, we call it two-way recursion

For example:

def binary_sum(S, start, stop):
    """
    二路递归计算一个序列的和，例如S[0:5],就像切片的范围一样

    """

    if start >= stop:
        return 0
    elif start == stop - 1:
        return S[start]
    else:
        mid = (start + stop) // 2
        return binary_sum(S, start, mid) + binary_sum(S, mid, stop)

This recursion will call the function twice every time it is executed, so it is a two-way recursion. After each recursion, the range is reduced by half, so the depth of the recursion is 1 logn

Multiple recursion

If a recursive call can start three or more other recursive calls, we call it multiple recursion

For example:

import os

def disk_usage(path):
    """
    计算一个文件系统的磁盘使用情况，

    """

    total = os.path.getsize(path)
    if os.path.isdir(path):
        for filename in os.listdir(path):
            childpath = os.path.join(path, filename)
            total += disk_usage(childpath)
    print(&#39;{0:<7}&#39;.format(total), path)
    return total

os.path .getsize is the real-time disk space used by the identified file or directory. What I understand is that if the identifier is a file, then the size of the file is obtained. If it is a folder, the size of the folder is obtained, but the contents of the folder are not included, just like a box. There are many items in it, but only the weight of the box is calculated here, but the weight of the items is not calculated, that is, an empty box is calculated. So the number of recursive calls in this recursive function depends on the number of files or folders in this layer, so it is multiple recursion.

The shortcomings of recursion

The shortcomings of recursion are obviously the consumption of time and space. In this article, the cache method is used to reduce the calculation of the Fibonacci sequence. Consumption, here we use another way to improve the bad recursion:

def fibonacci(n):
    """
    斐波那契数列计算，返回的是一个元组

    """

    if n <= 1:
        return (n, 0)
    else:
        (a, b) = fibonacci(n - 1)
        return(a + b, a)

Change the original two-way recursion to linear recursion, reducing repeated calculations.

Python’s maximum recursion depth

Each recursion will consume resources, and each consecutive call will require additional memory. When infinite recursion occurs, then It means rapid depletion of resources, which is obviously unreasonable. In order to avoid this phenomenon, python intentionally limits the depth of recursion during design. We can test it

def limitless(n):
    print('第' + str(n) + '次调用')
    n += 1
    return limitless(n)
limitless(1)

988th call
989th call
990th call
991st call
992nd call
993rd call
994th call
995th call
996th call
Traceback (most recent call last):
File “D:/github/Data-Structure/code/recursive.py”, line 73, in
limitless(1)
File “D:/github/Data-Structure/code /recursion.py", line 70, in limitless
return limitless(n)
File "D:/github/Data-Structure/code/recursion.py", line 70, in limitless
return limitless (n)
File “D:/github/Data-Structure/code/recursive.py”, line 70, in limitless
return limitless(n)
[Previous line repeated 992 more times]
File "D:/github/Data-Structure/code/recursion.py", line 68, in limitless
print('str(n)'th call')
RecursionError: maximum recursion depth exceeded while calling a Python object

finally recurses to 996 times and stops recursion, which means that Python's recursion depth is limited to around 1000.

The 1000-layer limit is enough, but it may still be limited to certain calculations, so python provides a way to modify the limit

import sys
def limitless(n):
    print('第' + str(n) + '次调用')
    n += 1
    return limitless(n)

print(sys.getrecursionlimit())#1000
sys.setrecursionlimit(2000)
limitless(1)

第1994次调用
第1995次调用
第1996次调用
Traceback (most recent call last):
 File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
   return limitless(n)
 File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
   return limitless(n)
 File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
   return limitless(n)
 [Previous line repeated 995 more times]
 File “D:/github/Data-Structure/code/递归.py”, line 68, in limitless
   print(‘第’ + str(n) + ‘次调用’)
RecursionError: maximum recursion depth exceeded while calling a Python objec

可见把这个深度该为2000后便多了1000次调用，但这个深度显然不是设置多少就是多少，毕竟还有计算机CPU与内存的限制，比如吧深度改为10000，那么运行后

第3920次调用
第3921次调用
第3922次调用
第3923次调用

Process finished with exit code -1073741571 (0xC00000FD)

到达3923次便终止了，查询-1073741571发现是递归栈溢出的问题。

尾递归

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

Python解释器在对于一次函数调用中，会使用一个栈帧来保存当前调用的函数的信息，如输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数。因此在递归的调用中，这种未执行完的函数会一层一层的占用大量的栈帧。如果将递归的调用放到函数执行的最后一步，那么执行完这步，该次函数的栈帧就会释放，调用函数的新栈帧就会替换掉之前的栈帧，所以无论调用的深度有多少次，都只会占用一个栈帧，那也就不会发生栈溢出的问题。这就是尾递归。

所以根据需要，尾递归必须是线性递归，并且递归调用的返回值必须立即返回。

拿一个阶乘递归函数举例

def factorial(n):
    """
    阶乘递归函数

    """
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

上边这个是一个普通的递归，下面把他改成尾递归的形式

def facttail(n, res):
    """
    阶乘尾递归，res初始为1

    """

    if n < 0:
        return 0
    elif n == 0:
        return 1
    elif n == 1:
        return res
    else:
        return facttail(n - 1, n *res)

这个函数比之前那个还多了个res，第一种每次调用完要乘n，这里的res就起了相同的作用，由于尾递归每一层的栈帧要释放，所以通过res来作为相乘的过程。我个人认为尾递归的难度就在于参数的设计，因为它的前提条件就是调用后什么也不再执行了，所以要作为传递的东西就得提前通过参数设计传递，总之要想设计一个尾递归的算法还是需要好好思考一下的。

The above is the detailed content of How to use Python to understand recursion (code explanation). For more information, please follow other related articles on the PHP Chinese website!