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

Question

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

Рейтинг: -1Ответов: 2Опубликовано: 05.08.2023

Смотрел ролики Тимофея Хирьянова по алгоритмам и структурам данных. Он использовал рекурсивный вызов внутри цикла, я не понял как.

Вот объясните пожалуйста, почему у нас например не происходит выхода из рекурсии, когда Х достигается 0, и почему именно такие X выводятся

python функции циклы рекурсия стек

Источник: Stack Overflow на русском

Answer 1

▲ 3

Нет "выхода из рекурсии". Есть вызов функции и что-то что происходит внутри. Больше ничего нет:

f(3)

f(3)
    print(3)
    f(2)
    print(3)
    f(2)

f(3)
    print(3)
    f(2)
        print(2)
        f(1)
        print(2)
        f(1)
    print(3)
    f(2)
        print(2)
        f(1)
        print(2)
        f(1)

f(3)
    print(3)
    f(2)
        print(2)
        f(1)
            print(1)
            f(0)
            print(1)
            f(0)
        print(2)
        f(1)
            print(1)
            f(0)
            print(1)
            f(0)
    print(3)
    f(2)
        print(2)
        f(1)
            print(1)
            f(0)
            print(1)
            f(0)
        print(2)
        f(1)
            print(1)
            f(0)
            print(1)
            f(0)

    print(3)
        print(2)
            print(1)
            print(1)
        print(2)
            print(1)
            print(1)
    print(3)
        print(2)
            print(1)
            print(1)
        print(2)
            print(1)
            print(1)

Answer 2

▲ 1

Может я попытаюсь пояснить

Вот объясните пожалуйста, почему у нас например не происходит выхода из рекурсии, когда Х достигается 0

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

def f(x, step_req):
    step_req+=1
    fn=-100
    if x==0:
        print(f'Возврат x={x}')
        return 0
    for i in range(2):
        print(f'Перед вызовом i={i}  Шаг рекурсии {step_req} x={x}')
        fn=f(x - 1, step_req)
        print(f'Точка возврата f()={fn} i={i}  Шаг рекурсии {step_req} x={x}')
print(f(3,0))

Перед вызовом i=0  Шаг рекурсии 1 x=3
Перед вызовом i=0  Шаг рекурсии 2 x=2
Перед вызовом i=0  Шаг рекурсии 3 x=1
Возврат x=0
Точка возврата f()=0 i=0  Шаг рекурсии 3 x=1
Перед вызовом i=1  Шаг рекурсии 3 x=1
Возврат x=0
Точка возврата f()=0 i=1  Шаг рекурсии 3 x=1
Точка возврата f()=None i=0  Шаг рекурсии 2 x=2
Перед вызовом i=1  Шаг рекурсии 2 x=2
Перед вызовом i=0  Шаг рекурсии 3 x=1
Возврат x=0
Точка возврата f()=0 i=0  Шаг рекурсии 3 x=1
Перед вызовом i=1  Шаг рекурсии 3 x=1
Возврат x=0
Точка возврата f()=0 i=1  Шаг рекурсии 3 x=1
Точка возврата f()=None i=1  Шаг рекурсии 2 x=2
Точка возврата f()=None i=0  Шаг рекурсии 1 x=3
Перед вызовом i=1  Шаг рекурсии 1 x=3
Перед вызовом i=0  Шаг рекурсии 2 x=2
Перед вызовом i=0  Шаг рекурсии 3 x=1
Возврат x=0
Точка возврата f()=0 i=0  Шаг рекурсии 3 x=1
Перед вызовом i=1  Шаг рекурсии 3 x=1
Возврат x=0
Точка возврата f()=0 i=1  Шаг рекурсии 3 x=1
Точка возврата f()=None i=0  Шаг рекурсии 2 x=2
Перед вызовом i=1  Шаг рекурсии 2 x=2
Перед вызовом i=0  Шаг рекурсии 3 x=1
Возврат x=0
Точка возврата f()=0 i=0  Шаг рекурсии 3 x=1
Перед вызовом i=1  Шаг рекурсии 3 x=1
Возврат x=0
Точка возврата f()=0 i=1  Шаг рекурсии 3 x=1
Точка возврата f()=None i=1  Шаг рекурсии 2 x=2
Точка возврата f()=None i=1  Шаг рекурсии 1 x=3
None

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

Ответы