Достигаем горизонт с замкнутой рекурсией

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

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

Показательным является применение рекурсии для вычисления факториала - f(n) = n*f(n-1). Раскручивая цепь, функция сможет найти ответ. Единственным нюансом является указать, что делать, когда достигнем n=1 => f(n)=1:

def f(n):
    if n==1 or n==0: 
        return 1
    else: return n*f(n-1)

Сам по себе механизм рекурсии трудно воспринимаем, а когда возникает необходимость возвращать результаты работы, голова начинает еще больше кипеть. И тут на помощь приходит замыкание (объявление функции внутри функции).

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

Так, чтение осуществляется свободно, а изменение происходит без проблем только для изменяемых типов, иначе нужно явно указать, что переменная из пространства имен функции родителя (ключевое слово nonlocal).

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

def prepare_walk(l1,l2):
    l1=l1
    l2=l2
    N = len(l1)
    steps_num=0
    level = 0
    res_l = []
    def walk(level=level):
        nonlocal steps_num
        if l1[steps_num] > l2[steps_num]:
            res_l.append((steps_num, 'l1_win', level))
        else:
            res_l.append((steps_num, 'l2_win', level))
        steps_num+=1
        if steps_num < N:
            walk(level+1)
        else:
            print('exiting')
        return res_l
    return walk

l1 = [1,2,-3]
l2 = [-2,10,2]
walk = prepare_walk(l1,l2)
walk()

Результаты аккумулируются в списке res_l (изменяемый тип и не требуется указания nonlocal). Для запоминания глубины рекурсии используется параметр функции (level), а для вывода количества шагов обычная переменная из области функции-родителя. В данном случае использование числа шагов и глубины рекурсии исключительно показательно, разница не заметна. Вместе с тем, если бы мы вызывали для if и else рекурсию отдельно (например, при реализации алгоритма дробления отрезка по частям ), то отличие было бы налицо.