Используя рекурсию по последовательности математических чисел?

Question

Я хочу использовать рекурсию для непрерывных дробей, которая будет выглядеть следующим образом.

Пользователь будет вводить значение n, а если n равно 3, то оно будет выглядеть так:

2 + 1 / (1 + 1 / (2 + 2 / (3 + 3/4))) *

где первые 2 + 1 / зафиксированы в уравнении, теперь мы должны вычислить числа за ним. Это та часть, где я несколько дней чесал голову. Кто-то учил меня, что можно использовать рекурсию для вычисления этой части, но я пытался научиться использовать ее, но моя просто зацикливается навсегда или имеет recursionError

n = int(input("Enter n value: "))
result = 0
fract = 0

def frac(j):
    global fract
    for i in range(j):
        fract = (j + j)/ frac(j)
    return fract

def calc_e():
    e = 2 + 1/ frac(n) / n + 1
    return e

print(calc_e())

#formula = 2 + 1 / (1 + 1 / (2 + 2 / (3 + 3 / (4 + 4 / (...)))))

TLDR: я не знаю, как рассчитать деталь после 2 + 1 /

Answer 1

У вас есть некоторые основные проблемы в вашей frac рутине

def frac(j):
    global fract
    for i in range(j):
        fract = (j + j)/ frac(j)
    return fract

• Вы не определились, как сообщить результат: вы продолжаете обновлять глобальный fract, но потом возвращаете его значение. Только один из них должен быть необходим.
• Аналогично, вы проходите через непрерывную дробь с и a for loop и рекурсией. Вы должны использовать только один из них.
• У вас нет базового варианта в вашей рекурсии: алгоритму нечего сказать, что он "достиг дна". Каждый раз, когда вы нажимаете на шаг вычисления, вы возвращаетесь к frac; нет логического пути, который не повторяется. Это основная причина, по которой вы получаете бесконечную рекурсию. Если это новые концепции для вас, пожалуйста, пройдите учебник по рекурсии; это объяснит это, по крайней мере, так, как мы можем здесь.
• Ваша алгебра неверна: (j + j)/ frac(j) неправильный порядок операций и дает вам просто 2*j / frac(j). У вас должно быть что-то вроде j + j/frac(j+1).

Достаточно ли намеков, чтобы привести вас к более полезной практике кодирования? Вам также может понадобиться помощь в отладке; несколько удачно выбранных print заявлений обычно покажут вам, что происходит. Смотрите этот прекрасный debug блог за помощью.

Answer 2

Нет необходимости использовать переменную global; Я не вижу, где возникает необходимость в for -петле. И, как указывалось в предыдущих ответах, у вас есть несколько ошибок алгебры.

Вы должны добавить аргумент условия остановки к frac, чтобы остановить его бесконечный повтор. Вернуть значение j, если это нажатие:

# max number of terms n
def frac(j, n):
    if j >= n: return n
    return j + j / frac(j+1, n)

# remember to pass 1.0 instead of 1, or cast to float in frac
# to avoid integer division which will truncate all fractions
def calc_e(n=100):
    return 2 + 1 / frac(1.0, n)

Возвращает:

n    calc_e(n)
----------------------
2    2.666666666666667
4    2.716981132075472
8    2.718281657666404
16   2.718281828459045
32   2.718281828459046
64   2.718281828459046
128  2.718281828459046
256  2.718281828459046
512  2.718281828459046

Большее количество рекурсий было невозможно из-за переполнения стека.

Answer 3

Вы можете использовать простую рекурсию:

#2 + 1/ (1 + 1 / (2 + 2/ (3 + 3 / 4)))
def get_equation(_to_val, string_rep = False):
   if string_rep:
     def calculate(start, end):
       return '{}+{}/({})'.format(start, start, calculate(start+1, end) if start < end else end+1)
     return '2+1/({})'.format(calculate(1, _to_val))
   def calculate(start, end):
      return start+start/(calculate(start+1, end) if start < end else end+1)
   return calculate(1, _to_val)


print(get_equation(3))
print(get_equation(3, True))

Выход:

1.3947368421052633
2+1/(1+1/(2+2/(3+3/(4))))