Как работают рекурсии?

Question

[Raddzor788]

def func(x):
    if x < 4:
        print(x)
        func(x+1)
    print(x)
func(1)

результат

1
2
3
4
3
2
1

как это работает? Я понимаю, как получилось 1,2,3,4, но как отсчет пошел назад 3,2,1 ? Этот момент, я вообще не могу понять! Как это происходит, как это работает под капотом? может кто подробно объяснить ?

Comments

[VoidVolker]

Raddzor788, Правила 3.8

Answer 1

[Vindicar]

Raddzor788,

Где хранятся все эти значение 1,2,3,4, ведь у моего 'x' нету же звездочки(*х), чтобы собрать столько аргументов.

Твой x - это несколько разных x. Потому что есть такая вещь как области видимости. Обычно есть область видимости функции (локальная) и глобальная область видимости скрипта. Если функция не видит нужного имени в локальной области - она ищет в глобальной. Если не видит и там - ищет в __builtins__.
0. По умолчанию есть глобальная область видимости скрипта.
1. При вызове func(1) создаётся локальная область видимости (скажем, А), в ней создаётся имя x, указывающее на 1.
2. Отработало условие 1 < 4.
3. Вызывается func(2). При этом создаётся НОВАЯ локальная область видимости Б (потому что новый вызов функции), в ней создаётся имя x, указывающее на 2.
4. Отрабатывает условие 2 < 4.
5. Вызывается func(3). При этом создаётся локальная область видимости В, в ней создаётся имя x, указывающее на 3.
6. Отрабатывает условие 3 < 4.
7. Вызывается func(4). При этом создаётся локальная область видимости Г, в ней создаётся имя x, указывающее на 4.
8. Условие 4 < 4 не отрабатывает. Происходит вызов print(x) - имя x находится в текущей локальной области Г, выводится ассоциированное с ним значение 4. Отрабатывает print(4), происходит возврат из функции, область видимости Г уничтожается.
9. Происходит вызов print(x) в предыдущем "слое" рекурсии. Текущая локальная область видимости В - в ней имя x связано со значением 3. Отрабатывает print(3), происходит возврат из функции, область видимости В уничтожается.
10. Происходит вызов print(x) в предыдущем "слое" рекурсии. Текущая локальная область видимости Б - в ней имя x связано со значением 2. Отрабатывает print(2), происходит возврат из функции, область видимости Б уничтожается.
11. Происходит вызов print(x) в предыдущем "слое" рекурсии. Текущая локальная область видимости А - в ней имя x связано со значением 1. Отрабатывает print(1), происходит возврат из функции, область видимости А уничтожается.
12. Мы вышли из всех слоёв рекурсии. Мы находимся в теле скрипта и работаем только с глобальной областью видимости.

Answer 2

[VoidVolker]

В данном случае происходит примерно следующее:

x=1
  print(1) <- if ветка и рекурсия
  x=2
    print(2) <- if ветка и рекурсия
    x=3
      print(3) <- if ветка и рекурсия
      x=4 
      print(4) <- мимо if - работает вторая часть функции
    print(3)
  print(2)
print(1)

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

def func(x1): # функция #1
    if x1 < 4:
        print(x1) # 1

        x2 = x1 + 1 # функция #2
        if x2 < 4:
            print(x2) # 2

            x3 = x2 + 1 # функция #3
            if x3 < 4:
                print(x3) # 3

                x4 = x3 + 1 # функция #4
                print(x4) # 4 

            print(x3) # 3, функция #3 - конец
        print(x2) # 2, функция #2 - конец
    print(x1) # 1, функция #1 - конец

Comments

[Raddzor788]

Извиняюсь, VoidVolker, я только изучаю синтаксис python и мне не очень понятны некоторый вещи.Если не сложно, то можно как-то по нагляднее? если не составит труда
'x' у меня изначально равен 1, потому что, я передаю туда 1 при вызове, и на четвертой строке<(это где func(x+1) )> получает x + 1 это уже 1 + 1? сразу ?. Где хранятся все эти значение 1,2,3,4, ведь у моего 'x' нету же звездочки(*х), чтобы собрать столько аргументов. Но что более не понятно, почему это все происходит 7 раз (1,2,3,4,3,2,1) ??? тут же нет итерации. Как происходит итерация? или это не итерация? объект функции не имеет метода iter. Вот после ""print(4) <- мимо if - работает вторая часть функции"" тоже не понятно.Почему именно так должно быть? почему идет откат назад? print(3), print(2), print(1) ???? почему должен работать обратный порядок?

[shurshur]

Raddzor788, в func делается print 2 раза: сначала в начале функции (до рекурсии), потом в конце функции (после рекурсии). В итоге каждая функция при значениях x меньше 4 делает два print, вставляя посередине рекурсию. Итог вполне очевиден.

[VoidVolker]

Raddzor788, потому что в каждом вызове переменная х - локальная для текущего вызова функции и такой она остаётся до конца выполнения функции. Я развернул код в упрощенный вид без рекурсии (не то же самое, только для значения 1). Итого получается функция вызывается четыре раза: сначала отрабатывает первая часть и выдаёт 1-2-3, а далее рекурсия останавливается и функция выдает 4, затем функция завершается и работу продолжает предыдущая функция, где выполняется вторая часть функции и она выдаёт 3, затем повторяется до самого первого вызова и получается в итоге 3-2-1.

Answer 3

[Alexandroppolus]

www.tvd-home.ru/recursion

Comments

[Raddzor788]

хороший сайт! но код не понятен. Это на каком языке? есть что-нибудь на python? буду благодарен, если найдется что-то понятное

[Alexandroppolus]

Raddzor788, это на Паскале. Если из тамошних примеров выкинуть слова begin/end, то ничем принципиально от Питона не будет отличаться - отступы в порядке.

по Питону ничего посоветовать не могу, сам-то я на TS пишу..