Рекурсия и поиск с возвратом

Описание принципа
Рекурсия - это вызов функции самой себя. Метод применяется для обхода графов или деревьев (таких как файловая система).
Задача Число Фибоначчи
Они задаются рекуррентным соотношением fi = f{i-1} + f{i-2}
Начальные условия обычно задаются как f0 = 0, f1 = 1

Задача: написать функцию, которая принимает целое число n и возвращает n-ное число Фибоначчи.

def fibonacci(n):
    SENTINEL = -1
    numbers = [SENTINEL] * (n + 1)

    def fibonacci(n):
        if n <= 1:
            return n
        elif numbers[n] != SENTINEL:
            return numbers[n]
        else:
            result = fibonacci(n - 1) + fibonacci(n - 2)
            numbers[n] = result
            return result
    return fibonacci(n)


if __name__ == '__main__':
    print(fibonacci(10))
Задача Число Фибоначчи
Дано число N, нужно сгенерировать все правильные скобочные последовательности из N открывающих и N закрывающих скобок.

При решении переборных задач результат иногда используются объекты-аккумуляторы, в которых храниться результат работы функции. В данном примере используется объект result.

def generate(n):
    result = []

    def generate_(left, right, accum):
        if not left and not right:
            result.append(''.join(accum))
            return
        if left:
            accum.append('(')
            generate_(left - 1, right, accum)
            accum.pop()
        if right > left:
            accum.append(')')
            generate_(left, right - 1, accum)
            accum.pop()

    generate_(n, n, [])
    return result


if __name__ == '__main__':
    print(generate(3))