Возврат в рекурсивной функции

Я только что начал изучать python (v3.2.3) и столкнулся с нечетной проблемой return в этой функции:

def test(x):
    if x > 9 :
        test(x - 10)
    else:
        print('real value',x)
        return x

x = int(input())
y = test(x)
print('this should be real value',y)

Когда я запустил его, я получаю:

45
real value 5
this should be real value None

Но я ожидал:

45
real value 5
this should be real value 5

Я попытался добавить return x вне if, и я получил значение ввода по умолчанию. Может ли кто-нибудь объяснить, как работает return?

Ответ 1

Вы вызываете test(45). Это проверяет, является ли 45 > 9 истинным, поэтому вызывает test(35) (45 - 10), не возвращая его результат. То же самое происходит с test(25) и test(15), пока не будет вызван окончательный test(5).

Это печатает "реальное значение 5", а затем возвращает 5. Но возврат результата из функции всегда возвращает его прямому вызывающему абоненту этой функции. Он не сразу перескакивает через несколько вызовов; в конце концов, вызывающий может захотеть что-то сделать с возвращенным результатом, прежде чем возвращать что-то своему вызывающему. Однако в этом случае только test(5) возвращает что-либо вообще; все остальные вызовите test(x - 10), дождитесь возврата, проигнорируйте все, что он возвращает, а затем (неявно) верните None. Поскольку самый внешний вызов test(45) является одним из этих случаев, вы получаете None.

Здесь делается попытка визуализации того, что происходит:

test(45):
| test(35):
| | test(25):
| | | test(15):
| | | | test(5):
| | | | | print('real value',5)
| | | | | return 5 to test(15)
| | | | return None to test(25)
| | | return None to test(35)
| | return None to test(45)
| return None

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

def test45(x):
    if x > 9 :
        test35(x - 10)
    else:
        print('real value',x)
        return x

def test35(x):
    if x > 9 :
        test25(x - 10)
    else:
        print('real value',x)
        return x

def test25(x):
    if x > 9 :
        test15(x - 10)
    else:
        print('real value',x)
        return x

def test15(x):
    if x > 9 :
        test5(x - 10)
    else:
        print('real value',x)
        return x

def test5(x):
    if x > 9 :
        print 'No more tests :('
    else:
        print('real value',x)
        return x

Функция теста (x), которую вы вызываете с помощью "x = 45", аналогична функции вызова test45(45). Надеюсь, вы можете понять, почему очевидно, что None должен быть возвращен, когда рекурсия не задействована. Ну, когда речь идет о рекурсии, ничего не меняется. Оператор return не знает и не заботится о том, возвращается ли он из рекурсивно вызываемой функции, он ведет себя точно так же в любом случае.

Фактически, рекурсия вообще не является чем-то особенным; он ведет себя точно так же, как обычные вызовы функций. Вы получаете информацию от того, что вызвало вас через аргументы, и вы возвращаете информацию к тому, что вызвало вас, вернувшись. Если вы не вернете что-то (возможно, только в одной руке if), тогда None будет возвращен вашему вызывающему абоненту, независимо от того, вызываете ли вы какую-либо другую функцию в этой ветке, вне зависимости от того, что эта функция может вернуться если вы вызываете что-то, и независимо от того, является ли вызываемая вами функция той же самой функцией, что вы внутри.

Ответ 2

Возврат с отступом, поэтому он выполняется только в ветке else. Если первая ветвь берется, функция неявно возвращает None.

Вам нужно изменить это на

return test(x-10)

Ответ 3

Вы забыли вернуть значение x > 9. Без возвращаемого значения функция будет "возвращаться" None.