Рекурсия. Погружаемся и всплываем

Чтобы понять рекурсию, надо понять рекурсию

известная среди программистов шутка.

Рекурсия одна из самых красивых и в то же время сложно постижимых умозрительным способом концепций программирования.

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

Но моя задача не запугать, а помочь понять один из нюансов рекурсии, а именно как порядок рекурсивного вызова влияет на данные которые мы получаем.

В этой статье мы посмотрим что будет, если вызвать рекурсию до основного действия (погружение) и после (всплытие).

Рассмотрим простой пример. Нам нужно вывести числа от 10 до 1 включительно, каждое на своей строке.

Наивный способ, который мы с вами знаем может выглядеть так:

for num in range(10, 0, -1):
    print(num)

Правда нам, для нашей задачи выгоднее его оформить в виде цикла while, с ним будет проще понять параллели с рекурсией.

num = 10
while num:
  print(num)
  num -= 1

Теперь мы можем поразмышлять над алгоритмом и написать нашу рекурсивную функцию сначала методом погружения, а потом и всплытия.

В первую очередь следует подумать над граничным условием, ведь рекурсия без граничного условия никогда не закончится. В нашем случае граничное условие – достижение минимально возможного значения единицы или нуля. В данном случае выбор граничного значения влияет только на то, будет ли совершен лишний “пустой” вызов, который не сделает ничего или мы сделаем ровно столько вызовов, сколько нужно напечатать чисел. Я предпочитаю не делать пустых вызовов, поэтому граничное значение установим равным единице.

Итак для начала нам нужно напечатать 10. Именно это число получит наша функция dive_in().

После того как мы напечатали число. нам надо проверить нужно ли печатать следующее. Так как 10 не 1, нам нужно напечатать следующее. Для того чтобы напечатать его мы просто вызовем функцию dive_in() с уменьшенным на единицу текущим значением. И будем так делать до тех пор, пока число, которое мы напечатали не будет равно единице. Обратите внимание, что мы сначала печатаем число, а потом опускаемся на следующий уровень (погружаемся). По есть действие выполяняется в момент погружения.

def dive_in(num):
    print(num)
    if num > 1:
        dive_in(num - 1)


dive_in(10)

Получим

10
9
8
7
6
5
4
3
2
1

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

Но можно ведь и сначала погрузиться на дно, и начать маркировать оттуда.

Тогда просто изменится взаимный порядок печати и вызова следующей итерации.

def dive_out(num):
    if num > 1:
        dive_out(num - 1)
    print(num)
    
    
    dive_out(10)

1
2
3
4
5
6
7
8
9
10

Обратите внимание, что теперь мы сначала вызываем функцию (погружаемся) и таким образом доходим до дна, и только потом, после того как достигли граничного значения (дна), выполняем действие (при всплытии). Подчеркну, действие выполняется в момент “всплытия”. Это очень важный аспект в рекурсии. Очень важно понимать, что в случае с рекурсией вы можете что-то делать до погружения (вызова рекурсии), а что-то после.

Но данная статья была бы неполной, без следующего шага – мы же пишем с вами функцию, а это значит, что мы хотим получить результат выполнения и, желательно такой, корый мы могли бы использовать дальше. А это значит что нас не устраивает print() и мы хотим на выходе получить полноценную строку, содержащую наш вывод.

Давайте модифицируем нашу функцию погружения.

def dive_in_new(num):
    if num > 1:
        return f'{num}\n{dive_in_new(num - 1)}'
    return f'{num}'
    
    
print(dive_in_new(10))

10
9
8
7
6
5
4
3
2
1

И всплытие.

def dive_out_new(num):
    if num > 1:
        return f"{dive_out_new(num - 1)}\n{num}"
    return f"{num}"


print(dive_out_new(10))

1
2
3
4
5
6
7
8
9
10

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

Заключение

Данная статья написана с единственной целью – помочь понять, как влияет на результат взаимный порядок вызова функции и основного действия.

Нужно понимать, что одни задачи требуют выполнения основного действия в процессе “погружения”, а другие в процессе “всплытия”. Бывают задачи, которые задействуют оба направления движения внутри рекурсии, но они встречаются гораздо реже. Умения выбрать правильное направление сродни езде на велосипеде из примера с которого я начал статью, и чтобы научиться понимать какой подход для каждой задачи выбрать, нужна практика, нужны падения и ошибки. Выбор неправильного подхода не делает задачу неразрешимой, но обрекает нас на чрезмерное усложнение задачи. И если задача с рекурсией кажется слишком сложной, то вероятно мы выбрали не то направление для основного действия. Прекрасный пример этой проблемы – задача Многочлен N-ой степени. Если пробовать ее решить в момент “погружения” (прямой порядок), то вам придется тащить в данные не только остаток строки но и накопленный результат. А при всплытии (обратный порядок) задача становится элементарной.
Этот пример лишний раз подтверждает ранее озвученную концепцию, что некоторые задачи в программировании легче решать с конца.