RecursionError: maximum recursion depth exceeded in comparison

@D303 · Регистрация: 28.07.2019

Студворк — интернет-сервис помощи студентам

Всем добрый вечер
Возникли проблемы с задачей.
Условие:
Найдите аналитическое выражение для $https://www.cyberforum.ru/cgi-bin/latex.cgi?{p}_{3}(n)$

Вход программы состоит из единственной строки — списка из не более чем ста тысяч чисел $https://www.cyberforum.ru/cgi-bin/latex.cgi?{n}_{i}\leq 2000000000$

Выведите единственную строку — список значений $https://www.cyberforum.ru/cgi-bin/latex.cgi?{p}_{3}({n}_{i})$ , разделенных пробелом, для чисел из входа.

Sample Input:
1 3 5
Sample Output:
0 1 2

Я работаю в PyScripter и у него с данным кодом проблем нет. Однако на платформе, в которой дано это задание этот код не принимается с таким вот поясненим:

[I]Failed test #2 of 11. Runtime error

Traceback (most recent call last):
File "jailed_code", line 19, in <module>
print(int(p(A)),end=' ')
File "jailed_code", line 15, in p
a=p(n-1)+p(n-2)-p(n-4)-p(n-5)+p(n-6)
File "jailed_code", line 15, in p
a=p(n-1)+p(n-2)-p(n-4)-p(n-5)+p(n-6)
File "jailed_code", line 15, in p
a=p(n-1)+p(n-2)-p(n-4)-p(n-5)+p(n-6)
[Previous line repeated 994 more times]
File "jailed_code", line 6, in p
if n==0 or n==1 or n==2:
RecursionError: maximum recursion depth exceeded in comparison

Как это исправить?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A=list(map(int,input().split()))
 
 
def p(n):
    if n==0 or n==1 or n==2:
        return 0
    if n==3 or n==4:
        return 1
    if n==5:
        return 2
    else:
        return  p(n-1) + p(n-2) - p(n-4) - p(n-5) + p(n-6)
 
for i in range(len(A)):
    print(int(p(A[i])),end=' ')

@unfindable_404 · 07.05.2020, 22:33

Может они вам отрицательное число подают? По условию число меньше или равно 2 * 10⁹. А про нижнюю границу ничего не сказано. А с отрицательным числом ваша функция уйдёт в бесконечную рекурсию.

@Welemir1 · 07.05.2020, 22:34

ну так у тебя для последнего варианта аж 5 раз рекурсивно вызывается функция

Сообщение от D303

return p(n-1) + p(n-2) - p(n-4) - p(n-5) + p(n-6)

можно лимит рекурсии увеличить, но не уверен что поможет

@unfindable_404 · 07.05.2020, 22:41

И ещё, используйте возможности языка по назначению. Цикл for предназначен для итерации по коллекциям.
Используйте его не так:

Python
1
2
for i in range(len(A)):
    print(int(p(A[i])),end=' ')

а так:

Python
1
2
for i in A:
    print(int(p(i)),end=' ')

Добавлено через 4 минуты
А что вообще за задача? Это всё условие?

@D303 · 08.05.2020, 00:59 **[ТС]**

Не подскажите, как это сделать?

Добавлено через 3 минуты
Да, это все условие. Разбиение числа на три слагаемых (порядок нам не важен)

Добавлено через 9 минут
Так, теперь ошибок нет. Но программа все равно не проходит 2 тест (в чемон заключается, я не знаю).

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A=list(map(int,input().split()))
 
 
def p(n):
    if n==-n:
        return (n**2)//12
    if n==0 or n==1 or n==2:
        return 0
    if n==3 or n==4:
        return 1
    if n==5:
        return 2
    if n==6:
        return 3
    else:
        
        return  (n**2)//12
 
for i in A:
    print(int(p(i)),end=' ')

@unfindable_404 · 08.05.2020, 13:03

Сообщение от D303

Да, это все условие. Разбиение числа на три слагаемых

На вход подаются три числа. На выходе тоже три. Так какое число надо разбить на слагаемые?
Объясните, пожалуйста, как вы понимаете задание, чтобы я тоже его понял.

@D303 · 08.05.2020, 13:30 **[ТС]**

На вход подается какое то количество чисел (в данном примере 3). И для каждого из них надо найти количество способов разбить его на 3 слагаемых (порядок нам не важен). И вывести количество разбиений для каждого из введеных чисед в строку
Пример разбиения числа 5: 1+1+3 , 1+2+2 - 2 способа

@Catstail · 08.05.2020, 14:15

В этом решении дикая параллельная рекурсия. Отсюда и проблемы. Радикально они решаются применением накопительных параметров:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def p_bad(n):
    if n==0 or n==1 or n==2:
        return 0
    if n==3 or n==4:
        return 1
    if n==5:
        return 2
    else:
        return  p_bad(n-1) + p_bad(n-2) - p_bad(n-4) - p_bad(n-5) + p_bad(n-6)
 
def p_good(n,arr=[0,0,0,1,1,2]):
    if (n<=5):
        return arr[n]
    else:
        z=arr[5]+arr[4]-arr[2]-arr[1]+arr[0]
        return p_good(n-1,arr[1:]+[z])
 
print(p_good(22))
print(p_bad(22))

@D303 · 08.05.2020, 14:30 **[ТС]**

Сообщение от Catstail

В этом решении дикая параллельная рекурсия. Отсюда и проблемы. Радикально они решаются применением накопительных параметров:

Ваш код также не хочет обрабатывать большие числа (по условию, верхняя граница это 20000000)
Эту проблему мне удалось решить, используя явную формулу для таких разбиений ( [n^2/12] - целая часть)

Сейчас проблема в другом, программа, тестирующая код, на 2 тесте выдает ошибку. В чем заключается этот тест, я не знаю.

Вот код

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
A=list(map(int,input().split()))
 
 
def p(n):
    if n==0 or n==1 or n==2:
        return 0
    if n==3 or n==4:
        return 1
    if n==5:
        return 2
    if n==-n:
        return  n**2//12
    else:
        return  n**2//12
 
for i in A:
    print(int(p(i)),end=' ')

Вот ссылка: https://stepik.org/lesson/11744/step/10?unit=2659

@Catstail · 08.05.2020, 16:30

Сообщение от D303

Эту проблему мне удалось решить, используя явную формулу для таких разбиений ( [n^2/12] - целая часть)

- я не занимался никакими разбиениями. Я имел дело только с кодом. Что он делает - не интересовался.

Добавлено через 14 минут
От рекурсии, кстати, легко отказаться. Но 20000000 циклов - это сильно.

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

@unfindable_404 693 / 471 / 204 Регистрация: 22.03.2020 Сообщений: 1,051
	07.05.2020, 22:33
	Может они вам отрицательное число подают? По условию число меньше или равно 2 * 10⁹. А про нижнюю границу ничего не сказано. А с отрицательным числом ваша функция уйдёт в бесконечную рекурсию. 0

@D303 0 / 0 / 0 Регистрация: 28.07.2019 Сообщений: 24
	08.05.2020, 13:30 [ТС]
	На вход подается какое то количество чисел (в данном примере 3). И для каждого из них надо найти количество способов разбить его на 3 слагаемых (порядок нам не важен). И вывести количество разбиений для каждого из введеных чисед в строку Пример разбиения числа 5: 1+1+3 , 1+2+2 - 2 способа 0