Поиск палиндрома

Необходимо разработать программу, которая реализует поиск палиндрома с использованием рекурсии. Палиндром - слово или фраза, которые одинаково читаются слева направо и справа налево.
Пользователем на вход подается строка, сгенерированная случайным образом (не более 30 символов, поддержка русского и английского языков, а также служебных символов ',.~`/?!@#$%^&*()_+ {}[]:;\| ).
Задача - найти максимальный палиндром во входной строке. Реализация поиска палиндрома должна быть с использованием рекурсии. Результатом работы программы будет:
Найденный максимальный палиндром.
Какие символы и на каких позициях должны быть удалены для получения максимального палиндрома.
Время работы алгоритма.
Если палиндромов несколько одинаковой длины, то программа выводит первый полученный палиндром.
Ограничение - нельзя использовать функции строк и любые функции, позволяющие определить палиндром, подстроку в строке, длину строки и пр. Можно использовать функции scanf, printf (или их аналоги).
Пример:
На вход подается строка 1q2wr3t5a3gw2plmq1
Выходное значение: 1q2w353w2q1.
Результат должен выглядеть следующим образом:
1q2w353w2q1
5 - r, 7 - t, 9 - a, 11 - g, 14 - p, 15 - l, 16 - m
Затраченное время: 0,0034576.