CS 61A Summer 2018 Lecture 07: Recursion about learning_list HOT 18 OPEN

# too big n will generate: [RecursionError: maximum recursion depth exceeded in comparison]
# not a valid algorythom
def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)
    
def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)
    
print(is_even(8))

def is_even(n):
    if n == 0:
        yield True
    yield is_odd(n - 1)
    
def is_odd(n):
    if n == 0:
        yield False
    yield is_even(n - 1)
    
print(is_even(8))

# 伪尾递归优化，性能太差，没法用
import types

def tramp(gen, *args, **kwargs):
    g = gen(*args, **kwargs)
    while isinstance(g, types.GeneratorType):
        g=next(g)
    return g
    
tramp(is_even, 8)

def cascade(n):
    if n < 10:
        print(n)
    else:
        print(n)
        cascade(n // 10)
        print(n)
    
cascade(1234)

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
        
print(fib(6))

def fib(n, cache_dict={}):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        if n in cache_dict:
            return cache_dict[n]
        cache_n = fib(n - 1) + fib(n - 2)
        cache_dict[n] = cache_n
        return cache_n
        
        
print(fib(6))

def fib(n):
    curr, next = 0, 1
    for _ in range(n):
        curr, next = next, curr + next
    return curr
        
        
print(fib(300))

def count_part(n, m):
    
    if n < 0:
        return 0
    if n == 0 and m > 0:
        return 1
    if m <= 0:
        return 0

    with_m = count_part(n - m, m)
    without_m = count_part(n, m - 1)
    return with_m + without_m
    
print(count_part(6, 3))