Вскоре после окончания Великой Отечественной войны Александр Михайлович Рекунков женился на Антонине Ивановне (урожденной Сучковой), с которой познакомился в госпитале. В 1946 году у них родилась дочь Наталья, а в 1958 году — сын Владимир.

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

Вспоминая те далекие годы, Александр Михайлович говорил:

«В августе 1945 года я, как и многие мои сверстники, прошедшие тяжкие годы войны, пришел в прокуратуру и попал, как иногда говорят, на другой фронт — борьбы с преступностью и другими нарушениями законности. Обстановка была сложной. Но помогала фронтовая закалка.

Наше поколение составило в те годы ядро прокурорских кадров, тот золотой фонд, который задавал тон в работе. Мы привыкли проявлять инициативу, быть решительными, брать ответственность на себя, не прячась за спины подчиненных или начальства, добиваться положительных результатов, и если убеждены в правоте, отстаивать дело до конца. Привыкли к дисциплине, что не означало слепого и бездумного подчинения, к порядку во всем — в отношениях к людям, к делу, а также, считаю уместным это сказать, к имуществу, к содержанию помещения. Даже внешний вид здания, чистота и порядок в нем создают определенное впечатление о стиле работы… Вспоминаю, как мы старались держать в чистоте здание моей первой районной прокуратуры… Запомнилась даже такая деталь: посетители, приходя в прокуратуру, снимали галоши еще в вестибюле и шли по коридору в чистой обуви. Граждане проникались уважением к учреждению, его сотрудникам. С другой стороны, и работников прокуратуры это обязывало быть собранными, внимательными, чуткими, что обеспечивало доверительный тон разговора, утверждало уверенность, что здесь найдешь защиту».

С самого начала работы в прокуратуре А. М. Рекунков остро ощутил отсутствие профессиональных знаний. Поэтому, почти сразу же после назначения, он поступил на трехмесячные курсы при Ростовской юридической школе, а в 1946 году — в Ростовский филиал Всесоюзного юридического заочного института, который окончил в 1952 году, сдав государственные экзамены на отлично.

28 декабря 1946 года А. М. Рекунков был переведен на должность помощника прокурора Целинского района. Он выступал в суде: по уголовным делам в качестве государственного обвинителя, по гражданским — давал заключения, готовил протесты на неправосудные приговоры, надзирал за расследованием дел, проверял обоснованность задержания подозреваемых в преступлениях лиц в камерах предварительного заключения, вел прием и рассматривал жалобы граждан и занимался другой работой.

В октябре 1947 года Александра Михайловича назначили на самостоятельную работу — прокурором небольшого Константиновского района Ростовской области. Характер его деятельности несколько изменился. Теперь надо было не только осуществлять надзорные функции, но и правильно организовать работу коллектива, самому принимать ответственные решения, давать санкции на арест людей. Как правило, он всегда лично допрашивал подозреваемых, перед тем как решить, отправлять их в тюрьму или нет. Много времени отнимала общенадзорная работа: проверки на предприятиях и в организациях, в колхозах и на машинно-тракторных станциях, выступления перед населением и в трудовых коллективах.