Функции и понятие рекурсии

Функции

Функция - такой же именованный объект, как и переменная, но в отличии от переменной, функция исполняет какое-то действия, используя при этом то, что в нее ввели, и возвращает результат ее работы.

Объявить функцию можно инструкцией def.

def sum(a, b):
    # Инструкция return возвращает результат
    # своего исполнения тому, кто её вызвал.
    return a + b
 

x = sum(1, 4) # x = 5


def noop():
    # Инструкция pass - это обозначение
    # "ничего-не-делания". Она нужна потому, что мы не можем
    # написать функцию, или любой другой блок кода,
    # (начинающийся с двоеточия), который
    # не имеет содержимого.
    # 
    # Это будет работать:
    pass
 

def noop():
    # А это сломается, тело-то пустое!
 

noop()

Кроме обычных функций в Python есть и анонимные функции, или лямбда-функции.

Они создаются с помощью инструктора lambda. Они не требуют return, так как вмещают в себя всего одно выражение, и исполняются быстрее. В остальном ведут себя так же как обычные функции.

sum = lambda x, y: x * 2 + y * 2
x = sum(1, 2)  # x = 1 * 2 + 2 * 2 = 2 + 4 = 6


Рекурсивная функция - это функция, которая в своём теле вызывает саму себя.
Пример такой функции:

def recursion_example(n):
    if n > 0:
        recursion_example(n - 1)
        print(str(n) + ": hello")

recursion_example(10)

В данном примере функция будет вести себя так, будто бы она содержит цикл от 1 до 10, и выведет это:

1: hello
2: hello
3: hello
4: hello
5: hello
6: hello
7: hello
8: hello
9: hello
10: hello

Ещё один простой пример, для чего ещё можно использовать рекурсию - Числа Фибоначчи:

def fib(n):
    if n > 1:
        return fib(n - 1) + fib(n - 2)
    else:
        return n


# 1 1 2 3 5 8 13 21 34 55 ...
a = fib(35)
print(a)

Или версия функции с кэшем, для предотвращения пересчёта первых чисел из последовательности при каждом вызове:

fib_cache = { }


def fib(n):
    if n > 1:
        if n not in fib_cache.keys():
            m = fib(n - 1) + fib(n - 2)
            fib_cache[n] = m
        return fib_cache[n]
    return n


# При первом вызове придётся пройти все
# 400 уровней глубины рекурсии...
a = fib(400)
print(a)
# А теперь функция рекурсивно вызывается
# всего единожды, результаты закешированы в словарь!
b = fib(401)
print(b)