Вскоре после окончания Великой Отечественной войны Александр Михайлович Рекунков женился на Антонине Ивановне Сучковой, с которой познакомился в госпитале. В 1946 году у них родилась дочь Наталья, а в 1958 году — сын Владимир.
После госпиталя Рекунков поехал долечиваться на родину. Послевоенная жизнь была тяжелая и голодная, поэтому долго лечиться ему не пришлось. В августе 1945 года боевой офицер по рекомендации Верхнедонского райкома партии был направлен на работу в органы прокуратуры. Александр Михайлович рассказывал автору книги, что в выборе места работы, он, конечно же, принимал участие. В то время сотрудники органов прокуратуры носили погоны, форменное обмундирование очень похожее на армейское, и ему, как человеку, мечтавшему стать офицером, это нравилось. Но решающую роль в выборе будущей профессии, безусловно, сыграла сама деятельность органов прокуратуры, которая в послевоенные годы была весьма заметной — ведь прокурорские работники вели войну на другом фронте, на фронте укрепления законности в стране и борьбы с преступностью. Так, Рекунков попал на работу в прокуратуру и стал помощником прокурора Верхнедонского района Ростовской области. С этого времени вся его жизнь оказалась связана с деятельностью этого ведомства. Он прошел большой путь от помощника районного прокурора до Генерального прокурора СССР
Вспоминая те далекие годы, Александр Михайлович рассказывал:
"В августе 1945 года я, как и многие мои сверстники, прошедшие тяжкие годы войны, пришел в прокуратуру… Обстановка была сложной. Но помогала фронтовая закалка.
Наше поколение составило в те годы ядро прокурорских кадров, тот золотой фонд, который задавал тон в работе. Мы привыкли проявлять инициативу, быть решительными, брать ответственность на себя, не прячась за спины подчиненных или начальства, добиваться положительных результатов и, если убеждены в правоте, отстаивать дело до конца. Привыкли к дисциплине, что не означало слепого и бездумного подчинения, к порядку во всем — в отношениях к людям, к делу, а также, считаю уместным это сказать, к имуществу, к содержанию помещения. Даже внешний вид здания, чистота и порядок в нем создают определенное впечатление о стиле работы… Вспоминаю, как мы старались держать в чистоте здание моей первой районной прокуратуры… Запомнилась даже такая деталь: посетители, приходя в прокуратуру, снимали галоши еще в вестибюле и шли по коридору в чистой обуви. Граждане проникались уважением к учреждению, его сотрудникам. С другой стороны, и работников прокуратуры это обязывало быть собранными, внимательными, чуткими, что обеспечивало доверительный тон разговора, утверждало уверенность, что здесь найдешь защиту".
С самого начала работы в прокуратуре Рекунков остро ощутил отсутствие профессиональных знаний. Поэтому почти сразу же после назначения он поступил на трехмесячные курсы при Ростовской юридической школе, а в 1946 году — в Ростовский филиал Всесоюзного юридического заочного института, который закончил в 1952 году, сдав все государственные экзамены на отлично.
В декабре 1946 года Рекунков был переведен на должность помощника прокурора более крупного Целинского района.
Рекунков часто выступал в суде. В октябре 1947 года его назначили на самостоятельную, так называемую процессуальную должность — прокурором небольшого Константиновского района Ростовской области. Характер его деятельности несколько изменился. Теперь надо было не только осуществлять надзорные функции, но и правильно организовать работу коллектива, самому принимать ответственные решения: давать санкции на арест людей, на обыски и выемки, утверждать обвинительные заключения и некоторые постановления следователей и т. п. Прокурором Ростовской области в то время был Полозков, юрист исключительно опытный. Деятельность Рекункова его вполне устраивала, и он, оценив активность, целеустремленность, трудолюбие молодого прокурора, зачислил его в резерв на выдвижение.
Вскоре Александр Михайлович возглавил прокуратуру более крупного Азовского района той же области. Не давал спуску никому и карал виновных, невзирая на должности. И здесь у него начались первые серьезные стычки.
В то время партия была "руководящей и направляющей" силой общества. Авторитет же партийцев, входивших в бюро даже районного комитета, считался непререкаемым. Они почти всегда и во всем диктовали свои условия. Не каждый осмеливался вступать с ними в открытую борьбу. Однако однажды молодой прокурор пошел ва-банк. Он возбудил уголовное дело непосредственно против некоторых членов бюро райкома, обвиняя их в хищениях и злоупотреблениях. На такой шаг не всегда отваживались даже опытные прокуроры.