Я написал рекурсию которая каждый раз делила отрезок на два и брала максимальный среди ответа всех таких отрезков которых поделила.(типо Merge Sort). У меня был memory limit на 3 тесте. Это значить рекурсия берет память?

Да, берёт. Рекурсия хранит итерации в стеке.

Не знаю, работает ли это с рекурсией, но для очистки ненужной памяти можно использовать эту библиотеку (если на Python):
import gc
gc.collect() # убираем ненужное

Там был тест на n = 0. Я тоже пытался решить через разделяй и властвуй и на n = 0 у меня все падало