Проблема с рекурсией в VSC

Question

Немного не могу понять почему программма, не выдавая ошибки с проблемой, связанной с глубиной рекурсии просто выходит, ничего не выводя. Написал я код на visual studio code, и получаетается вот такая проблема, но если запустить код в pycharm, то программа выводит результат. С чем может быть это связано. Вот код:

import sys
import functools
sys.setrecursionlimit(11000000)
@functools.lru_cache(None)
def f(n):
    if n>=10000:
        return n
    elif n<10000 and n%3==0:
        return n+f(n/3)
    
    return 2*n +f(n+3)

print(f(46))

Вот так выглядит запуск программ в VSC

Answer 1

Там разные методы оптимизации в VCS и Pycharm, попробуй этот код

import sys
import functools

sys.setrecursionlimit(11000000)

@functools.lru_cache(None)
def f(n):
    if n >= 10000:
        return n
    elif n < 10000 and n % 3 == 0:
        return n + f(n // 3)

    return 2 * n + f(n + 3)

print(f(46))

Answer 2

Почему в PyCharm работает а в VSCode нет, сказать не могу. Возможно вызываются разные версии Питона или в различных конфигурациях.

К делу. Лимит в 11000000 рекурсивных вызовов - это чрезмерно много. Интерпретатор Питона запускается с фиксированным размером стека. Чтобы его померить я использую такую программу:

import sys


def rec(n):
    if n > 1:
        rec(n - 1)


n = int(input())
sys.setrecursionlimit(n)
rec(n - 10)

Потом подбираю число при котором всё рушится:

$ echo 14500 | python depth.py

$ echo 14600 | python depth.py
Segmentation fault (core dumped)

У меня предел между 14500 и 14600. Ставить большие значения смысла нет. У вас пределы могут быть другими, но точно не одиннадцать миллионов. Для кода из вопроса достаточно 14000. Задача решена.

Прежде чем идти дальше, починим неточность в делении. n / 3 в Питоне возвращает вещественное число даже если n делится на три без остатка. Не большая ошибка, но без неё проще работать. Правим на целочисленное деление - n // 3.

Функция f кэширована. Кэш можно заполнить, чтобы избежать переполнения стека при вычислении. Например так:

import functools


@functools.lru_cache(None)
def f(n):
    if n >= 10000:
        return n
    elif n < 10000 and n % 3 == 0:
        return n + f(n // 3)
    return 2 * n + f(n + 3)


error = True
while error:
    print('populating cache...')
    error = False
    for n in range(1, 10000):
        try:
            f(n)
        except RecursionError:
            error = True

print(f(46))

Блок в середине пытается заполнить кэш для значений [1, 10000). Если произошла ошибка, заполнение кэша повторяется c начала. После пятого цикла кэш заполнен:

$ python f.py
populating cache...
populating cache...
populating cache...
populating cache...
populating cache...
33332674

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

До сих пор мы не обращали внимания на то как устроена функция f. Два наблюдения:

если n не делится на три, то рекурсивный вызов будет для большего значения и это значение снова не будет делиться на три;
если n делится на три, рекурсивный вызов будет для меньшего значения. Важно что это убывание короткое: каждый раз значение делится на три. Любое число меньше 10000 быстро придёт к единице или к другому значению, которое на три не делится.

Отсюда идея: заполнить кэш для всех n, которые не делятся на три и заполнить его от больших значений к меньшим:

import functools


@functools.lru_cache(None)
def f(n):
    if n >= 10000:
        return n
    elif n < 10000 and n % 3 == 0:
        return n + f(n // 3)
    return 2 * n + f(n + 3)


for n in reversed(range(1, 10000)):
    if n % 3 != 0:
        f(n)

print(f(46))

Это работает быстро и без страшного кода с обработкой переполнения стека.

На последок покажу можно переписать функцию без рекурсии. Для Питона это важно: стек мелкий, глубокая рекурсия - зло.

Сперва перепишем рекурсию на хвостовую:

def g(n, acc):
    if n >= 10000:
        return acc + n
    elif n < 10000 and n % 3 == 0:
        return g(n // 3, acc + n)
    return g(n + 3, acc + 2 * n)


def f(n):
    return g(n, 0)

Потом отрефакторим:

def g(n, acc):
    if n >= 10000:
        return acc + n
    if n < 10000 and n % 3 == 0:
        acc += n
        n //= 3
    else:
        acc += 2 * n
        n += 3
    return g(n, acc)


def f(n):
    return g(n, 0)

Потом переделаем в цикл:

def f(n):
    acc = 0
    while n < 10000:
        if n % 3 == 0:
            acc += n
            n //= 3
        else:
            acc += 2 * n
            n += 3
    return acc + n

БЛОГ НА HUSL

Проблема с рекурсией в VSC

Ответы (2 шт):