Recursion

ComposingPrograms 1.7 Exercises

 

def countdown(n):
    print(n)
    if n>1:
        countdown(n-1)

def countup(n):
    if n>0:
        countup(n-1)
        print(n)

def recursive(m,n):
    if n>0:
        return m + recursive(m, n-1)
    else:
        return 0

def expt(base, power):
    if power==0:
        return 1
    else:
        return base * expt(base, power-1)

def sum_digits(n):
    if n<10:
        return n
    else:
        return n%10 + sum_digits(n//10)

def is_prime(n, d):
    if n<=1:
        return False
    elif d==1:
        return True
    elif n%d==0:
        return False
    else:
        return is_prime(n, d-1)

def sum_primes_up_to(n):
    if n==2:
        return 2
    elif is_prime(n, n-1):
        return sum_primes_up_to(n-1) + n
    else:
        return sum_primes_up_to(n-1)

递归和信用卡的Luhn算法

这里用python做一个mutual recursion

 

def split(n):
    return n//10, n%10

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

def luhn_double_sum(n):
    rest, last = split(n)
    luhn_digit = split(2*last)[0] + split(2*last)[1]
    if n<10:
        return luhn_digit
    else:
        rest, last = split(n)
        return luhn_sum(rest) + luhn_digit