Грокаем алгоритмы

Рекурсивные функции тоже используют стек вызовов! Посмотрим, как это делается, на примере функции вычисления факториала. Вызов factorial(5) записывается в виде 5! и определяется следующим образом: 5! = 5*4*3*2*1. По тому же принципу factorial(3) соответствует 3*2*1. Рекурсивная функция для вычисления факториала числа выглядит так:

def fact(x):

  if x == 1:

    return 1

  else:

    return x * fact(x-1)

В программу включается вызов fact(3). Проанализируем этот вызов строку за строкой и посмотрим, как изменяется стек вызовов. Стоит напомнить, что верхний блок в стеке сообщает, какой вызов fact является текущим.

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

Стек играет важную роль в рекурсии. В начальном примере были представлены два решения поиска ключа. Вспомните, как выглядел первый:

В этом случае все коробки лежат в одном месте и вы всегда знаете, в каких коробках еще нужно искать ключ.

Но в рекурсивном решении никакой кучи не существует.

Если кучи нет, то как ваш алгоритм узнает, в каких коробках еще нужно искать? Пример:

К этому моменту стек вызовов выглядит примерно так:

«Куча коробок» хранится в стеке! Это стек незавершенных вызовов функции, каждый из которых ведет собственный незаконченный список коробок для поиска. Стек в данном случае особенно удобен, потому что вам не нужно отслеживать коробки самостоятельно — стек делает это за вас.

Стек удобен, но у него есть своя цена: сохранение всей промежуточной информации может привести к значительным затратам памяти. Каждый вызов функции занимает не много памяти, но если стек станет слишком высоким, это будет означать, что ваш компьютер сохраняет информацию по очень многим вызовам. На этой стадии есть два варианта:

• Переписать код с использованием цикла.

• Иногда можно воспользоваться так называемой хвостовой рекурсией. Это непростая тема, которая выходит за рамки книги. Вдобавок она поддерживается далеко не во всех языках.

Упражнения

3.2 Предположим, вы случайно написали рекурсивную функцию, которая бесконечно вызывает саму себя. Как вы уже видели, компьютер выделяет память в стеке при каждом вызове функции. А что произойдет со стеком при бесконечном выполнении рекурсии?

Шпаргалка

• Когда функция вызывает саму себя, это называется рекурсией.

• В каждой рекурсивной функции должно быть два случая: базовый и рекурсивный.

• Стек поддерживает две операции: занесение и извлечение элементов.

• Все вызовы функций сохраняются в стеке вызовов.

• Если стек вызовов станет очень большим, он займет слишком много памяти.

4. Быстрая сортировка