python-027-递归-求序列最大值、计算第n个调和数、转换

递归，emmmmmmm，拥有一种魅力，接近人的立即思维，容易理解，又不容易理解。

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

但是，递归的使用要根据相应的成本来看，每次递归python解释器都会给一个空间来记录函数活动状态。但是有时候内存成本很高，有时候将递归算法转为非递归算法是一种好办法。

当然我们可以换解释器、使用堆栈数据结构等方法，来管理递归的自身嵌套，减小储存的活动信息，来减小内存消耗。

尾递归：返回结果只有函数本身的那种情况，且必须是线性递归。这我现在页不太明白，不多说。

最近算法学到了递归这一块，写了三个课后习题：

求序列最大值

给一个序列S，其中包含n个元素，用递归查找其最大值。

def max_of_s(s, n):
    """
    max= {s[0]                     n = 0
         {s[0:n-1]和s[n]中的最大值   n >= 1

    :param s: 含有n+1个数的列表
    :param n: 列表长度-1，列表最后一个元素的索引
    :return: 返回列表的最大值
    """
    if len(s) == 0: # 列表为空，返回None
        return None
    if n == 0:           # 达到递归的基本情况：列表只有一个元素，最大值为s[0]
        return s[0]
    tmp_max = max_of_s(s, n-1)
    return tmp_max if tmp_max > s[n] else s[n] # 每次返回MAX(前n个数的最大值，最后一个元素)


s = [1, 2, 4, 5, 66, 3, 8, 22, 8, -1, 0]
print(max_of_s(s, len(s)-1))

输出：

image.png

求第n个调和数

调和数：Hn = 1 + 1/2 + 1/3 + ··· + 1/n

def harmonic_number(n):
    """
    计算第n个调和数
    Hn = 1 + 1/2 + 1/3 + ··· + 1/n
    :param n: n
    :return: 第n个调和数
    """
    if n == 1:
        return 1
    return harmonic_number(n-1) + 1/n


print(harmonic_number(1))
print(harmonic_number(2))
print(harmonic_number(10))
print(harmonic_number(100))

输出：

image.png

把一串数字转换为对应的整数

例如："12345"<class 'str'> 转换为12345<class 'int'>

def string_to_int(s, n):
    """数字到整数"""
    if n == 0 :
        return int(s[n])
    return string_to_int(s, n-1) * 10 + int(s[n])


s = '12345'
x = string_to_int(s, len(s)-1)
print(x)
print(type(x))

输出：

image.png

递归分为线性递归、二路递归、多路递归。