Вложенная рекурсивная функция в python

Question

Я попытался реализовать вложенную рекурсивную функцию в python, она выдает ошибку «RuntimeError: превышена максимальная глубина рекурсии», вы можете увидеть эту функцию в следующем коде. ваша помощь в вопросе приветствуется.

n=10 

def test(n): 
    if n<=0: 
     return 1 
    else: 
     return test(test(n-1)+1) 

print test(n) 

Answer 1

Одна очень важная часть рекурсии является то, что при каждом рекурсивном вызове вы должны получить ближе к вашему якорной случай, который в данном случае является:

if n<=0: 
    return 1 

Однако, с кодом вы не приближаются к этому делу. Проблема эта линия:

return test(test(n-1)+1) 

Поскольку тест возвращается 1, когда он достигает конечный случай и добавить 1 к этому результату, давайте посмотрим, что происходит, когда мы называем test(2):

Дела якоря не и вы идете прямо в else. Вы возвращаетесь

test(test(1)+1) 

с 2-1=1. Ваш внутренний вызов теста также собирается идти в else случае и называют:

test(test(0)+1) 

Здесь ваш внутренний вызов теста возвращает 1 (он уже достиг конечного случая), что означает, что по существу в этой линии вы звоните

test(2) //test(1+1) 

еще раз. Здесь вы можете видеть, что ваша рекурсия никогда не заканчивается, следовательно, ваш maximum recursion depth exceeded error.

Просто чтобы прояснить, как вы могли бы сделать этот код (который, очевидно, просто пример) работы:

def test(n): 
    if n <= 0: 
     return 1 
    else: 
     return test(test(n-1)-1) //notice the -1 instead of +1 

Развейте вопрос:

Почему меняется рекурсивный вызов для тестирования (тест (п -2)) также приводят к бесконечной рекурсии?

Ну, это в основном по той же причине, что я указал прямо в начале. Вам нужно приблизиться к вашему делу. Хотя вы можете найти случай n<=0 внутри вложенного рекурсивного вызова test(n-2), вы можете не дойти до него во внешнем вызове функции.

Обратите внимание, что ваша функция возвращает 1, когда она достигает его конца дело, так что даже если test(n-2) не вызывает больше рекурсии возвращает 1 (а не 0), что означает, что вы в конечном итоге с

test(1) 

который снова вызовет бесконечный цикл (так как вы не можете заставить n быть <= 0 для этого вызова внешней функции).

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

if n <= 0: 
    return 0 

или

if n <= 1: 
    return 1 //you could also return any other value <= 1