Recursion

Recursive Functions

定义：在函数体中直接或间接调用自身的函数叫递归函数

即在执行函数体时还会调用若干次函数自身

递归函数的结构：

def头定义
条件语句用来判断基本条件，无递归调用（递归出口）
递归条件用来递归调用

判断递归是否正确：

验证基本条件
将递归函数看作函数抽象
假设f(n-1)正确，验证f(n)的正确性

e.g.1:用递归求各位数字和

def split(n):
    """把n分成最后一位与其他位两部分"""
    return n//10, n%10

def sum_digits(n):
    """求和各位数字"""
    if n<10:
        return n
    else:
        all_but_last,last = split(n)
        return sum_digits(all_but_last)+last

e.g.2:阶乘（使用diagram）

递归与迭代

递归转换到迭代：弄清需要通过迭代保持的状态

迭代转换到递归：迭代保持的状态可以通过参数传递

互递归（Mutual Recursion）

e.g. Luhn Algorithm

改算法常用于信用卡等的校验码计算，步骤如下：

步骤 1：反转数字

算法首先通过反转您正在检查的数字的数字。

步骤 2：每隔一个数字翻倍

从左侧的第一个数字开始（由于反转，现在是原始数字的最后一个数字），对每个第二个数字进行翻倍。

步骤 3：求乘积的数字之和

如果翻倍后的数字大于 9，则将乘积的数字相加（例如，翻倍 8 得到 16，因此相加 1 + 6 = 7）。

步骤 4：将所有数字相加

在上述操作后，将所有数字相加。

步骤 5：检查是否能被 10 整除

如果总和能被 10 整除（即以 0 结尾），则该数字根据 Luhn 算法是有效的。否则，它是无效的。

def split(n):
    """把n分成最后一位与其他位两部分"""
    return n//10, n%10

def sum_digits(n):
    """求和各位数字"""
    if n<10:
        return n
    else:
        all_but_last,last = split(n)
        return sum_digits(all_but_last)+last

def luhn_sum(n):
    if n<10:
        return n
    else:
        all_but_last, last = split(n)
        return luhn_sum_double(all_but_last)+last

def luhn_sum_double(n):
    all_but_last, last = split(n)
    luhn_digit = sum_digits(2*last)
    if n<10:
        return luhn_digit
    else:
        return luhn_sum(all_but_last)+luhn_digit

这里使用互递归让分离出来的数字奇数位不执行乘二操作，偶数位执行乘二操作

红魔咖啡馆

【CS61A】CS61A——Recursion