Ошибка рекурсии.Возникли проблемы с пониманием логики с рекурсивными функциями

Question

from functools import lru_cache

@lru_cache(maxsize=1000)
def recursiveFunc(x):
    if x == 1:
        return 1
    elif x > 1 :
        return recursiveFunc(x) + recursiveFunc(x+1) #This is the part i'm having doubts about. 

for x in range(1, 101):
     print(x, ":", recursiveFunc(x))

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

Answer 1

Здесь я постараюсь прояснить для вас вещи:)

Написание функции, которая перечисляет числа от 1 до n, очень просто.Если бы мы попытались запустить эту функцию

def recursiveFunc(i):
   print(i)
   recursiveFunc(i+1)

recursiveFunc(1)

Она бы распечатала 1, затем 2, 3 .... Но никогда не остановится.

1
2
3
...

Чтобы исправить это, мы добавим секундупараметр

def recursiveFunc(i, n):
   if i > n:
      return

   print(i)
   recursiveFunc(i+1)

recursiveFunc(1, 100)

Эта функция выйдет из функции, когда она пройдет n, в данном случае 100

1
2
...
100

, если вы хотите вернуть серию, а не просто распечатать ее, вы можете сделатьчто-то вроде этого:

def recursiveFunc(i, n):
   if i >= n:
      return str(i)

   return str(i) + ", " + str(recursiveFunc(i + 1, n))

print(recursiveFunc(1, 100))

Тогда результат будет

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100

Answer 2

Ваша проблема в том, что вы должны очень хорошо выучить всю историю рекурсии, это требует времени ... вы должны визуализировать, что программа выполняет на каждом этапе.Мой совет - сначала рисовать буфер стека при каждом вызове функции

---

Решение вашей проблемы:

def recursiveFunc(x):
    if x == 1:
        return 1
    elif x > 1 :
        return 1 + recursiveFunc(x-1) #This is the part I've changed.

for x in range(1, 101):
    print(x, ":", recursiveFunc(x))

Почему ваш не работает?Потому что когда функция вызывает return, return запускает новую функцию recursiveFunc (x) ... но это точно так же, как и раньше!так что есть бесконечный цикл.Более того, если вы добавите как recursiveFunc (x + 1) и передадите положительный x, вы никогда не сделаете сравнение x == 0, потому что x это растущий вызов после вызова.