Мой код выдает логическую ошибку с рекурсией, и я не знаю, как ее исправить

Question

def k_comp(n):
  n_new = 0
  if n == 0:
      n_new = 2
  if n == 1:
      n_new == 1
  if n > 1:
      n_new = (k_comp(n-1) + k_comp(n-2))**2
  return n_new

def Kseq(start, stop, step):
""" (int,int,int) -> list of integers
Kseq(0,6,1)--->
[2, 1, 9, 100, 11881, 143544361]
Kseq(2,6,2)---->
[9, 11881]


"""

  final_list = []
  append_this = 0
  for i in range (start,stop,step):
      append_this = k_comp(i)
      final_list.append(append_this)

  return final_list

print(Kseq(0,6,1))

Вместо ожидаемого вывода он печатает: [2, 0, 4, 16, 144, 16384]

Код должен делать это: Input: эта функция передается start (>= 0), значения stop (> start) и step (> = 1), которые определяют последовательность чисел.Выход: эта функция возвращает список соответствующей последовательности K.Последовательность k имеет вид k (n) = (k (n-1) + k (n-2)) ^ 2

Answer 1

Ваша проблема связана со вторым if условием в k_comp(), == - это тест на равенство:

if n == 1:
    n_new == 1

Это оставляет n_new = 0, поэтому я предполагаю, что вы имели в виду:

if n == 1:
    n_new = 1

После внесения изменений:

In []:
Kseq(0, 6, 1)

Out[]:
[2, 1, 9, 100, 11881, 143544361]

Примечание: это будет очень неэффективно, поскольку он вычисляет k_comp(k) несколько раз, вы можете просто построить последовательность k, например ::

def k_seq():
    k = [2, 1]
    for _ in range(2, n):
        k.append((k[-1] + k[-2])**2)
    return k

def Kseq(start, stop, step):
    return k_seq(stop)[start::step]

In []
Kseq(0, 6, 1)

Out[]:
[2, 1, 9, 100, 11881, 143544361]

In []:
Kseq(2, 6, 2)

Out[]:
[9, 11881]

Разница во времени:

In []:
%timeit Kseq_recursive(0, 10, 1)

Out[]:
75.8 µs ± 1.28 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In []:
%timeit Kseq_sequence(0, 10, 1)

Out[]:
4.39 µs ± 77.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

или как генератор

import itertools as it

def k_gen():
    kprime, k = 2, 1
    yield from (kprime, k)
    while True:
        kprime, k = k, (kprime + k)**2
        yield k

def Kseq(start, stop, step):
    return list(it.islice(k_gen(), start, stop, step))

In []:
Kseq(0, 6, 1)

Out[]:
[2, 1, 9, 100, 11881, 143544361]

Answer 2

Вы перепутали назначение и равенство в k_comp

У вас есть:

if n == 1:
   n_new == 1

Вы должны иметь:

 if n == 1:
     n_new = 1

Single '=' означает присвоение значения справа переменной слева.

Double '==' означает, что левое значение и правое значение равны. В этом случае будет идти не равно, поэтому False. False является допустимым оператором python; он просто не будет делать то, что вы ожидаете.