Созданная функция не работает (Python)

Question

Я довольно новичок в python, и я попытался использовать его, чтобы сделать программу для определения n-го термина для последовательности Stern-Brocot (вы можете посмотреть, что , и именно поэтому моя функция называется SBSeq). По какой-то причине, он не будет работать, и он приходит с ошибками, например:

File "C:/Python27/Factorials.py", line 6, in SBSeq 
return ((n%2)*SBSeq(ceil(n/2)-1))+SBSeq(ceil(n/2)) 

который в конечном счете идет на это:

File "C:/Python27/Factorials.py", line 5, in SBSeq 
if n == 1: return 1 
RuntimeError: maximum recursion depth exceeded in cmp 

Это исходный код.

import math 
from math import ceil 

def SBSeq(n): 

if n == 1: return 1 
return ((n%2)*SBSeq(ceil(n/2)-1))+SBSeq(ceil(n/2)) 

Любая помощь будет оценена!

Answer 1

Предполагая, что вопрос отступа не является реальной проблемой, проблема в том, что ваши номера могут достигать ниже 1 при переходе рекурсивен, а затем, как только он достигает ниже 1 (то есть п достигает 0), он держит на вызов SBSeq рекурсивно без выход.

Условие в начале рекурсивной функции должно быть if n <= 1 : return 1.

код -

def SBSeq(n): 
    if n <= 1: return 1 
    return ((n%2)*SBSeq(ceil(n/2)-1))+SBSeq(ceil(n/2)) 

Answer 2

SBSeq(2) звонки SBSeq(0), SBSeq(0) вызовы SBSeq(-1) и SBSeq(-1) звонки SBSeq(-1) навсегда.

Просто добавьте специальный чехол для SBSeq(0).

Answer 3

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

Это улучшенная функция:

import math 
from math import ceil 

def SBSeq(n): 
    if n <= 1: return 1 # not n == 1 
    return ((n%2)*SBSeq(ceil(n/2)-1))+SBSeq(ceil(n/2))