Почему выводит RecursionError: maximum recursion depth exceeded in comparison?

Question

[ysgmikey]

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

Задача

Определите наименьшее значение суммы n+m такое, что значение F(n, m) больше числа 15 и выполняется условие n≠m, n и m – натуральные числа. Запишите в ответе сначала значения n и m, при которых указанная сумма достигается, в порядке неубывания, а затем – соответствующее значение F(n, m). Числа в ответе разделяйте пробелом.

Код, данный в задаче:

def F(n,m):
 if n<m:
  n,m = m,n
 if n != m: 
   return F(n-m,m)
 else: 
   return n

Traceback (most recent call last):
  File "main.py", line 12, in <module>
    if F(a, b) > 15 and a != b and a + b < minnm:
  File "main.py", line 5, in F
    return F(n-m, m)
  File "main.py", line 5, in F
    return F(n-m, m)
  File "main.py", line 5, in F
    return F(n-m, m)
  [Previous line repeated 995 more times]
  File "main.py", line 2, in F
    if n < m:
RecursionError: maximum recursion depth exceeded in comparison

Мое решение:

def F(n, m):
 if n < m:
    n, m = m, n
 if n != m:
    return F(n-m, m)
 else:
    return n
minnm = 0
for a in range(1, 10000):
  for b in range(1, 10000):
    if F(a, b) > 15 and a != b and a + b < minnm:
        print(a, b, F(a, b))
        minnm = a + b

Answer 1

[Rsa97]

[Previous line repeated 995 more times]
То есть, у вас глубина стека ограничена 1000 вызовов. Если проанализировать функцию, то видно, что при n = 1 и m > 1 глубина стека вызовов будет m.
Таким образом у вас два варианта - переписать функцию или ограничить циклы до ~990.
Кроме того, функция симметрична относительно порядка аргументов. Значит внутренний цикл можно начитать не с 1, а с a+1.

Ну или решить задачу аналитически.

Данная функция реализует алгоритм нахождения наибольшего общего делителя методом Евклида. F(n, m) = X означает, что n = iX, m = jX, где i и j - натуральные числа и
i != j.
n + m = (i + j)X.
Минимальная пара i и j будет 1 и 2. Минимальное значение X, большее 15 будет 16.
Получаем n = 16, m = 32, F(16, 32) = 16, n + m = 48.