Прокурора Ростовской области Полозкова работа А. М. Рекункова вполне устраивала, и он зачислил его в резерв на выдвижение. Спустя пять лет, Рекунков возглавил прокуратуру более крупного района той же области, Азовского. Он все так же был решителен и инициативен, строг и требователен к нарушителям закона. Он не давал спуску никому и карал, невзирая на должности. Известно, что в советское время партия была «руководящей и направляющей» силой общества, а авторитет партийцев, входивших в бюро даже районного комитета — непререкаем. Они всегда и во всем диктовали свои условия. Редко кто из прокуроров отваживался вступать с ними в открытую борьбу. А Рекунков, став прокурором Азовского района, не побоялся возбудить против некоторых членов бюро райкома уголовное дело, обвиняя их в хищениях. На такой шаг не всегда отваживались даже опытные областные прокуроры. Началось давление, звонки в Прокуратуру Союза ССР, откуда приехала специальная бригада во главе с заместителем Генерального прокурора СССР Н. И. Хохловым. Представительная комиссия признала, что дело было возбуждено обоснованно. Однако до суда Рекунков это дело не довел. После смерти Сталина была объявлена широкая амнистия, и его пришлось прекратить. Но виновные все же понесли наказание — они были исключены из партии.

Горячность молодого прокурора иногда его подводила. В октябре 1953 года прокурор Ростовской области Иванов в своем приказе указал ему на то, что он «несерьезно относится к привлечению граждан к судебной ответственности». Поводом для такого «разноса» послужило прекращение уголовного дела в отношении двух возчиков угля, арестованных Рекунковым, а также оправдание судом троих граждан, обвинявшихся в хищениях. Однако такие случаи в практике А. М. Рекункова были крайне редки.

Несмотря на случавшиеся отдельные «проколы», Рекунков твердо руководил районной прокуратурой. Новый прокурор Ростовской области Иванов был о нем самого хорошего мнения, считая грамотным юристом и квалифицированным прокурором, дисциплинированным, инициативным и принципиальным. Поэтому не случайно Рекункова, набравшего солидный опыт работы в 1958 году назначили заместителем прокурора Брянской области. А уже через два года он возглавил эту прокуратуру. Распределяя обязанности, Александр Михайлович оставил за собой самые ответственные участки: руководство отелами общего надзора, по надзору за рассмотрением в суда х уголовных и гражданских дел, а также за исполнением законов по делам несовершеннолетних и в местах лишения свободы.

В 1966 году А. М. Рекункова перевели на должность прокурора Воронежской области. И здесь ему не раз приходилось проявлять характер. Во время одного из заседаний бюро обкома партии, на котором делал сообщение Рекунков, некоторые лица попытались оказать на него давление, требуя прекращения неприятного для руководства области уголовного дела. Когда Александр Михайлович исчерпал все доводы, приведенные в обоснование позиции следствия, но так и не смог убедить членов бюро, что дело надо расследовать до конца, то он встал, положил на стол перед первым секретарем обкома это дело и заявил, что если они так считают, то пусть ведут следствие по этому делу сами. Демарш произвел впечатление, и после этого случая никто уже не пытался так откровенно нажимать на прокурора области.

Прокурором Воронежской области А. М. Рекунков пробыл один конституционный срок, получив за работу орден Трудового Красного Знамени, а затем был переведен в центральный аппарат на должность первого заместителя прокурора республики. Одновременно он стал и членом коллегии Прокуратуры РСФСР. В аппарате он осуществлял контроль за работой отдела по надзору за рассмотрением в суда х уголовных дел, а также хозяйственного и финансового отделов и многое сделал для улучшения их деятельности.