菜鸟追梦旅行

这个屌丝很懒，什么也没留下！

热门标签

第四章递归 python实现 ( 数据结构与算法 from Goodrich）_python 多条数据多个元素比对用递归吗

作者：菜鸟追梦旅行 | 2024-04-04 03:00:17

踩

python 多条数据多个元素比对用递归吗

算法设计的递归方法的主要优点在于：它能使我们能够简洁地利用重复结构呈现诸多问题。通过使算法描述以递归的方式利用重复结构，我们经常可以避开复杂的案例分析和嵌套循环。这种方法会得出可读性更强的算法描述，而且十分有效。

一般而言，描述迭代的一种方法是使用循环（如while循环和for循环），另外一种比较常用的迭代实现方法是递归。递归是一种技术，这种技术通过一个函数在执行过程中一次或者多次调用其本身，或者通过一种数据结构在其表示中依赖于相同类型的结构更小的实例。自然生活中也有很多例子，例如：俄罗斯套娃。

下面的框架是如下：
一、四个使用递归的方法的例证

1. 阶乘函数(4-1 factorial(n)) 【O(n)】

2.英式标尺(4-2 draw_line(tick_length,tick_label=‘ ’))

3. 二分查找(4-3 binary_search(data,target,low,high)) 【O(log n)】但顺序查找：【O(n)】

4.计算机的文件系统(4-5 disk_usage(path)) 【O(n)】

二、递归算法的不足：

1.元素唯一性问题（4-6 uniques3(S,start,stop), 4-7 bad_fibonacci(n), 4-8 good_fibonacci(n)）

2.无限递归问题

三、递归的其他例子

1. 线性递归：阶乘函数 + 高效的斐波那契数列【O(n)】+ 二分查找【O(log n)】 + 4-9 linear_sum(S,n) 递归求和【O(n)】+ 4-10 reverse(S,start,stop) 递归逆序【O(n)】+ 4-11 power(x,n) 计算幂的递归【O(n)】+ 4-12power(x,n) 使用重复的平方计算幂函数【O(log n)】

2.二路递归：4-13 使用二路递归计算一个序列的元素之和 binary_sum(S,start,stop) 【O(log n)】

3.多重递归：文件系统属于一个多重递归问题【O(n)】

四、消除尾递归

4-15 二分查找算法的非递归实现

4-16 使用迭代逆置一个序列元素

正文部分：

一、四个使用递归的方法的例证

1. 阶乘函数：对于任何整数 $n\geqslant 0$ ，

$n! = \left\{\begin{matrix} 1 & n=0 \\ n\times (n-1) \times(n-2) \times \cdots \times3\times2\times1& n\geqslant 1 \end{matrix}\right.$

可以写成递归的形式：

$n! = \left\{\begin{matrix} 1 & n=0\\ n \times (n-1)!& n\geq 1 \end{matrix}\right.$


# 4-1 阶乘函数的递归实现
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

该函数不使用任何显示循环。迭代是通过函数的重复递归调用来实现的。可采用递归跟踪的形式来说明一个递归函数的执行过程。

2.英式标尺(4-2 draw_line(tick_length,tick_label=‘ ’))


# 4-2 绘制标尺
def draw_line(tick_length, tick_label=''):
    line = '-' * tick_length
    if tick_label:
        line += ' ' + tick_label
        print(line)
 
def draw_interval(center_length):
    if center_length > 0:
        draw_interval(center_length - 1)
        draw_line(center_length)
        draw_interval(center_length)
 
def draw_ruler(num_inches,major_length):
    draw_line(major_length,'0')
    for j in range(1,1+num_inches):
        draw_interval(major_length-1)
        draw_line(major_length,str(j))

3. 二分查找(4-3 binary_search(data,target,low,high)) 【O(log n)】但顺序查找：【O(n)】

该算法用于下一个含有n个元素的有序系列中有效定位目标值。延伸：当序列是无序时，使用循环实现顺序查找算法，是【O(n)】的时间复杂度；但当序列是有序时，可采用递归的思想进行二分查找【O(log n)】


# 4-3 二分法查找算法的实现
def binary_search(data, target, low, high):
    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)  # 递归到右边查找

4.计算机的文件系统(4-5 disk_usage(path)) 【O(n)】

现代操作系统用递归的方式来定义文件系统目录，，即一个文件系统包括一个顶级目录，这个目录的内容包括文件和其他目录，其他目录又可以包含文件和其他目录，以此类推。虽然必定会有一些基本的目录只包含文件而没有下一级子目录，到那时操作系统允许嵌套任意深度的目录（只要内存中拥有足够的空间）。

python 的操作系统模块：os模块

os.path.getsize(path):返回由字符串路径标识的文件或者目录使用的即时磁盘空间大小(单位：字节)

os.path.isdir(path): 如果字符串路径指定的条目是一个目录，则返回True;否则返回False.

os.listdir(path):返回一个字符串列表，它是字符串路径指定的目录中所有条目的名称。

os.path.join(path,filename): 生成路径字符串和文件名字串，并使用一个适当的操作系统分隔符在两者之间分割，返回表好似文件完整路径的字符串。


# 4-5 报告一个文件系统磁盘使用情况的递归函数
import os
def disk_usage(path):
    total = os.path.getsize(path)  # 首先定位相应路径path
    if os.path.isdir(path):  # 判断是否为目录
        for filename in os.listdir(path):    # 遍历目录下的文件
            childpath = os.path.join(path,filename)  # 生成相应新的文件名称
            total += disk_usage(childpath)
    print('{0:<7}'.format(total), path)
    return total

二、递归算法的不足：

虽然递归算法是一种非常强大的工具，但它也很容易被误用。

1.元素唯一性问题（4-6 uniques3(S,start,stop), 4-7 bad_fibonacci(n), 4-8 good_fibonacci(n)）


# 4-6 测试元素唯一性的递归函数（低效率）
def unique3(S,start,stop):
    if stop - start <= 1:
        return True
    elif not unique3(S,start,stop-1):
        return False
    elif not unique3(S,start+1, stop,):
        return False
    else: 
        return S[start] != S[stop-1]

斐波那契数列： $\\F_0 = 0\\ F_1 = 1 \\ F_n = F_{n-2} + F_{n-1} for n>1$


# 4-7 使用二分递归计算第n个斐波那契数列
def bad_fibonacci(n):
    if n <= 1:
        return n
    else:
        return bad_fibonacci(n-2) + bad_fibonacci(n-1)

这是一种效率非常低的计算方式，以这种计算方式计算第n个斐波那契数需要对这个函数进行指数级别的调用。


# 4-8 使用线性递归计算第n个斐波那契数
def good_fibonacci(n):
    if n <= 1:
        return (n,0)
    else:
        (a,b) = good_fibonacci(n-1)
        return (a+b,a)  # (F_n,F_(n-1))

这种递归的每次调用只进行一次递归调用。定义了一个如上的新的递归函数，该函数返回一对连续的斐波那契数列 $(F_{n},F_{n-1})$ ,并且使用约定 $F_{n-1}=0$ ,而不是让函数返回第n个斐波那契数这一单一数值。用返回一对连续的斐波那契数列代替返回一个值。

2.无限递归问题

在递归的误用中，另一个危险就是所谓的无限递归。如果每个递归调用都执行另一个递归调用，而最终没有达到一个基本情况，那么就有一个无穷级数的此类调用。python解释器就会生成一个RuntimeError消息：超过最大递归深度（Maximum recursion depth exceeded).

三、递归的其他例子

如下考虑在一个激活的函数体内开始的递归调用的最大数量来组织我们的介绍：

1.如果一个递归函数调用最多开始一个其他递归调用，我们称之为“线性递归”，例如：阶乘递归，高效的斐波那契数列，二分法查找的递归实现，递归求和，递归逆序，计算幂的递归算法。


# 4-1 阶乘函数的递归实现
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
 
# 4-3 二分法查找算法的实现
def binary_search(data, target, low, high):
    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)  # 递归到右边查找
 
# 4-8 使用线性递归计算第n个斐波那契数
def good_fibonacci(n):
    if n <= 1:
        return (n,0)
    else:
        (a,b) = good_fibonacci(n-1)
        return (a+b,a)  # (F_n,F_(n-1))

元素序列的递归求和


# 4-9 [O(n)]
def linear_sum(S,n):
    if n == 0:
        return 0
    else:
        return linear_sum(S,n-1) + S[n-1]

使用递归逆置序列


# 4-10 使用线性递归逆置序列的元素 [O(n)]
def reverse(S,start,stop):
    if start < stop -1:
        S[start],S[stop-1] = S[stop-1],S[start]
        reverse(S,start+1,stop-1)

用于计算幂的递归算法

幂函数（power function）: $power(x,n)=x^n$

写成递归的形式：

$power(x,n)=\left\{\begin{matrix} 1 &n=0 \\ x\cdot power(x,n-1)& else \end{matrix}\right.$


# 4-11 用简单的递归计算幂函数 [O(n)]
def power(x,n):
    if n == 0:
        return 1
    else:
        return x * power(x,n-1)

对于该问题，有一个更快的方法用以计算幂函数，即采用了平方技术的定义：假设 $k=\left \lfloor \frac{n}{2} \right \rfloor$

当n是偶数时， $\left \lfloor \frac{n}{2}\right \rfloor=\frac{n}{2}$ ,因此 $(x^k)^2=(x^{\frac{n}{2}})^2=x^n$ ;

当n是奇数时， $\left \lfloor \frac{n}{2}\right \rfloor=\frac{n-1}{2}$ 且 $(x^k)^2 =x^{n-1}$ ，因此 $x^n =x\cdot (x^k)^2$

综上：

$power(x,n) = \left\{\begin{matrix} 1 & n=0\\ x\cdot (power(x,\left \lfloor \frac{n}{2} \right \rfloor))^2& n >0 odd \\ (power(x,\left \lfloor \frac{n}{2} \right \rfloor))^2& n >0 even \end{matrix}\right.$


# 4-12 使用重复的平方计算幂函数[O(logn)]
def power(x,n):
    if n == 0:
        return 1
    else:
        partial = power(x, n//2)
        result = partial * partial
        if n % 2 == 1:
            result *= x
        return result

2.如果一个递归调用可以开始两个其他递归调用，我们称之为“二路递归”，例：英式标尺 + bad_fibonacci + 用二路递归计算一个序列的元素之和


# 4-13 用二路递归计算一个序列的元素之和 [O(logn)空间]
def binary_sum(S,start,stop):
    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)

3.如果一个递归调用可以开始三个或者更多其他递归调用，我们称之为“多重递归”。

例子：文件系统 disk_uage(path)

四、消除尾递归

在一般情况下，我们可以使用堆栈数据结构，通过管理递归结构自身的嵌套，而不是依赖于解释器，从而把递归算法转化为非递归算法。虽然这只是把内存使用从解释器变换到堆栈，但也许能够通过只存储最小限度的必要信息来减少内存使用。更好的情况是：递归的某些形式可以在不使用任何辅助存储空间的情况下被消除。其中一种著名的形式就是尾递归：如果执行的任何递归调用是在这种情况下的最后操作，而且通过封闭递归，递归调用的返回值立即返回，那么这个递归就是一个尾递归。根据需要一个尾递归必须是一个线性递归。

尾递归例子有：4-3的binary_search函数，4-10的reverse函数；而4-1的阶乘函数、4-9的linear_sum函数和4-7的good_fibonacci函数均不是尾递归例子。

在重复循环中，通过封闭函数体，并且通过重新分配现存参数的这些值以及用新的参数来代替一个递归调用，任何尾递归都可被非递归地重新实现。如下例：

1）4-3尾递归的binary_search函数的非递归实现：


# 4-15 二分查找算法的非递归算法的实现
def binary_search_iterative(data,target):
    low = 0
    high = len(data)-1
    while low <= high:
        mid = (low + high)//2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return False

同样可以对4-1尾递归的reverse函数的非递归实现：


# 4-16 使用迭代逆置一个序列的元素
def reverse_iterative(S):
    start,stop =0, len(S)
    while start < stop-1:
        S[start],S[stop-1] = S[stop-1],S[start]
        start,stop = start+1,stop-1

即是许其他线性递归不是正式的尾递归函数，他们也可以非常有效的利用迭代来转换表示。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/357148

第四章 递归 python实现 ( 数据结构与算法 from Goodrich）_python 多条数据 多个元素 比对 用递归吗

正文部分：

第四章递归 python实现 ( 数据结构与算法 from Goodrich）_python 多条数据多个元素比对用递归吗