Рекурсивный вызов в цикле?

Question

[qw1klyy]

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

def f(x):
    if x==0:
        return 0
    for i in range(2):
        print(x)
        f(x-1)
print(f(3))

Каким образом выводится X и почему он никогда не равняется нулю???

Comments

[Алан Гибизов]

Очевидно, из-за бесконечной рекурсии. А Бесконечная рекурсия потому, что цикл никогда не доходит до return.

[Алан Гибизов]

Возьмите листочек, ручку, и пропишите шаг за шагом, как меняется состояние переменных в вашем цикле. Это не сложно, и вы все поймёте.

[qw1klyy]

Алан Гибизов, а None выводится, потому что заканчивается цикл?

[Zzzz9]

Алан Гибизов, Вполне доходит;

def f(x):
    if x == 0:
        print('Дошел до 0')
        return 0
    for i in range(2):
        print('x',x)
        f(x - 1)
print('only', f(3))

x 3
x 2
x 1
Дошел до 0
x 1
Дошел до 0
x 2
x 1
Дошел до 0
x 1
Дошел до 0
x 3
x 2
x 1
Дошел до 0
x 1
Дошел до 0
x 2
x 1
Дошел до 0
x 1
Дошел до 0
only None

[Алан Гибизов]

Zzzz9, странно, надо наверно мне листочек взять :)
Ну в таком случае наверно return-ов меньше, чем рекурсивных вызовов...

[qw1klyy]

Zzzz9, вот, это я и имел в виду, просто не ясно выразился, у нас идет сначала 3 2 1 0 а потом опять 1, потом 0 потом 2 1. Откуда он после нуля возвращает 1 и 2 1 и каким образом он это делает?

[qw1klyy]

qw1klyy, и почему, после того ка он достиг нуля, нас не выкидывает из рекурсии?

[Zzzz9]

Алан Гибизов, это другое дело, при каждом вызове функции, она вызывается еще два раза, но все равно проблема не в этом, просто при возврате 0, функция просто заканчивается ничего не куда не возвращается. Но функция нормально завершается и ничего не зацикливается. Функция f(x - 1) вызывается и сюда же возвращается и просто заканчивается.

[Zzzz9]

qw1klyy, Цикл заканчивается, но ничего не возвращается, нужно после цикла сделать еще один return с каким-нибудь смыслом..

Answer 1

[Максим Припадчев]

x - равняется 0 в твоем коде. Перенеси print(x) в самый верх и увидишь. Рекурсия это бесконечный цикл вызова функцией самой себя, до тех пор пока базовое состояние не прервет его (одно или несколько). None ты в конце видишь потому что это printтебе его возвращает, у тебя уже есть print внутри функции.

def f(x):
    print(x)
    if x==0:
        return 
    else:
        f(x-1)         
f(3)

. В твоем случае он тоже выйдет и return 0 он выполняет, замени return на pass и получишь бесконечную рекурсию.

Насчет None у тебя вот такая ситуация print(print(1))

ОТРЕДАКТИРОВАНО После дискусии с Zzzz9, выяснилось, что я не прав насчет None. Базовый кейс в рекурсии останавливает рекурсию, но не выходит из функции. Что бы мы вернули значение базового кейса нам нужно добавить return к рекурсивному случаю. Например

def f(x):
    if x==0:
        return 100
    else:
        f(x-1)
print(f(3))

Вот так выход из рекурсии настает, но рекурсивный кейс не имеет return и функция вернет None а вот в такой вариации

def f(x):
    if x==0:
        return 100
    else:
        return f(x-1)
print(f(3))

Функция вернет 100. Насчет print я полную глупость написал, он возвращает None и я подумал, что это имеет место. Глупость полная. если мы добавляем return к рекурсивному кейсу то выведет то что возвращает базовый кейс. А базовый кейс только останавливает рекурсию но не выходит из функции.

Насчет цикла если мы добавим return к рекурсивному кейсу то for цикл выполнится только один раз, потому что базовый кейс остановит рекурсию а рекурсивный кейс имеет return соответсвенно, функция напечатает изменение x + один добавочный 0, который возвращает return в базовом кейсе. Например

def f(x):
    print(x)
    if x==0:
        return 'Конец'
    for i in range(10):
        return f(x-1)
print(f(3))

Цикл выполнится лишь раз и затем выход из функции.

Comments

[Zzzz9]

Что происходит после else: f(x-1)? Ничего, поэтому None

[Максим Припадчев]

Zzzz9, Нет None не будет запусти код. None приходит не из рекурсии, а если еще print сделать.

[Zzzz9]

Максим Припадчев, запусти

def f(x):
    pass
print('only', f(3))

only None

[Максим Припадчев]

Zzzz9, Ну твоя функция не имеет return, а моя имеет. Ты мой код запусти и никакого None там не будет. Потому что print получается двойной отсюда и None. Мой код запусти без print, как я опубликовал и там нет None. Хватит это элементарные вещи.

[Zzzz9]

Максим Припадчев, Просто ответь, что происходит после else: f(x-1) ? я отвечаю, Ничего, по этому None

[Zzzz9]

def f(x):
    if x==0:
        return
    else:
        f(x-1)
print(f(3))

None

[Максим Припадчев]

Zzzz9, Ладно, я смотрю тебе бесполезно, после происходит новый вызов функции затем когда x==0 возвращает True происходит выход.

[Zzzz9]

Куда? else: f(x-1)?

[Максим Припадчев]

Все пишу последний раз по шагово.
x = 3
первое условие False
else функция вызвала сама себя
x = 2
первое условие False
else функция вызвала сама себя
x = 1
первое условие функция False
else функция вызвала сама себя
x = 0
первое условие True выполняется return выход из из рекурсии.
На том все.

def f(x):
    print(x)
    if x==0:
        return 
    else:
        f(x-1)
f(3)

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

[qw1klyy]

Максим Припадчев, ну это понятно как работает, я просто пытаюсь разобраться как это работает в цикле

[Максим Припадчев]

Zzzz9, Извиняюсь, ты молодец действительно. Return в базовам случая не выходит из функции. Он останавливает рекурсию, но не выходит из функции. Был не прав, нужно к рекурсивному случаю добавить return иначе действительно None. Базовый кейс только для рекурсии не для выхода. Век живи век учись.

def f(x):
    print(x)
    if x==0:
        return 1
    else:
        return f(x-1)
print(f(3))

Если мы уберем у рекурсивного случая return то функция вернет None. Базовый кейс не прерывает функцию, а лишь только останавливает рекурсию. Еще раз извиняюсь.

[Zzzz9]

Да все нормально, вместе мы сильнее

[Максим Припадчев]

Zzzz9, Ну я на то и отвечаю, что бы выявить у себя слабые места. Почему то в голове замкнуло, что return наступил а значит выход из функции, а нет сюрприз, рекурсия остановлена ДА, выход из функции НЕТ.