def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

print(fact(3))

def s(lst):
    if not lst:
        return 0
    return lst[0] + s(lst[1:])

print(s([1, 2, 3]))

def rev(s):
    if len(s) <= 1:
        return s
    return rev(s[1:]) + s[0]

print(rev("abc"))

def digits(n):
    if n < 10:
        return 1
    return 1 + digits(n // 10)

print(digits(1234))

def tail_sum(n, acc=0):
    if n == 0:
        return acc
    return tail_sum(n - 1, acc + n)

print(tail_sum(5))

cache = {}

def fib(n):
    if n in cache:
        return cache[n]
    if n <= 1:
        cache[n] = n
    else:
        cache[n] = fib(n - 1) + fib(n - 2)
    return cache[n]

print(fib(6))

def count_items(lst):
    count = 0
    for item in lst:
        if isinstance(item, list):
            count += count_items(item)
        else:
            count += 1
    return count

print(count_items([1, [2, 3], [4, [5]]]))

tree = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': [],
    'D': []
}

def walk(node):
    print(node)
    for child in tree[node]:
        walk(child)

walk('A')

def gen(n):
    if n == 0:
        yield 0
    else:
        yield from gen(n - 1)
        yield n

print(list(gen(3)))

def search(d, target):
    for k, v in d.items():
        if k == target:
            return v
        if isinstance(v, dict):
            result = search(v, target)
            if result is not None:
                return result
    return None

data = {'a': {'b': {'c': 42}}, 'x': 1}
print(search(data, 'c'))