Жестокая, но неизбежная ловушка самовызовов и бесконечных циклов
Рекурсия
Мы можем столкнуться с ситуациями, связанными с циклами, когда мы не знаем требуемого количества итераций. В таких ситуациях мы заканчиваем тем, что используем циклы While, а не циклы for. Еще один способ справиться с этой ситуацией — «Рекурсия».
В этой статье я делюсь базовой реализацией рекурсии с использованием Python. Мне было скучно разглядывать примеры Факториала тут и там в Интернете. Поэтому подумал о том, чтобы реализовать то же самое на основе Happy Numbers (звучит так весело, правда? Я тоже сейчас улыбаюсь, печатая это).
Что такое рекурсия
Рекурсия — это метод компьютерного программирования, включающий использование процедуры, подпрограммы, функции или алгоритма, который вызывает сам себя на шаге. Просто, верно?
Ну, перечитай определение, не чувствуешь ли ты себя немного неловко, читая его?
Точно, я тоже. Если мы создадим функцию, которая вызывает сама себя, мы получим бесконечный цикл. Мы не хотим оказаться в этой ситуации. Чтобы выйти из этого порочного круга, нам нужно обеспечить некоторое условие завершения, при выполнении которого рекурсия остановится, и окончательный результат будет доставлен.
Переопределение рекурсии
Рекурсия — это техника компьютерного программирования, включающая использование процедуры, подпрограммы, функции или алгоритма, которые вызывают себя на шаге, имеющем условие завершения, так что последовательные повторения обрабатываются до критического шага, на котором выполняется условие, после чего остальная часть каждого повторения обрабатывается от последнего вызванного до первого. (Ссылка Ссылка)
Arghhh, слишком долго, чтобы понять правильно, давайте рассмотрим это на практике. Давайте попробуем решить задачу из теории чисел, чтобы лучше понять.
Попробуем выяснить, является ли данное число СЧАСТЛИВЫМ или нет.
Что такое СЧАСТЛИВОЕ число???
Если сумма квадратов его цифр равна 1, число счастливо, как 1, 10, 100 и т. д.
Но проблема на этом не заканчивается, если сумма квадратов цифр суммы квадратов фактического числа равна 1, мы все еще можем назвать исходное число счастливым.
Например, возьмем 68, сумма квадратов равна 6² + 8² = 36 + 65 = 100. Но, продолжая, сумма квадратов 100 равна 1² + 0 + 0 = 1. Следовательно, мы можем утверждать, что 68 — это СЧАСТЛИВОЕ число. . Надеюсь, вы чувствуете здесь необходимость рекурсии.
Ну, давайте попробуем какое-нибудь другое число, например, возьмем 11, сумма квадратов равна 2, сумма квадратов 2 равна 4, сумма квадратов 4 равна 16, сумма квадратов 16 равна 37, сумма квадратов 16 равна 37. 37 равно 58, сумма квадратов 58 равна 89, сумма квадратов 89 равна 145, сумма квадратов 145 равна 42, сумма квадратов 42 равна 20, И СУММА КВАДРАТ 20 равна 4…. И все это продолжает повторяться. Как мы знаем, видите, у нас уже было 4 как сумма квадратов, мы знаем, что 4 ведет в конечном итоге обратно к 4, это никогда не достигнет 1.
Именно это можно использовать в качестве конечного условия для прерывания рекурсии. Если для введенного числа рекурсия приводит к повторению суммы квадратов, выйти из рекурсии.
С этим мы можем перейти к практическому аспекту рекурсии. Пожалуйста, убедитесь, что вы знакомы с функциями, прежде чем двигаться дальше.
Краткое введение в функции и операторы return в Python, самостоятельно, ссылка на GitHub 😆 😜
Реализация Python
Что делает функция???
Короче говоря, в строке 13 функция happy_check() вызывает сама себя. Но единственная разница в том, что при дальнейшем вызове аргумент обновляется как часть предыдущих строк, выполняемых внутри функции. И, наконец, УСЛОВИЕ ЕСЛИ заботится о БАЗОВОМ СЛУЧАЕ, что гарантирует, что функция не будет вызываться снова при выполнении определенного условия.
Полный код доступен на GitHub
Поздравляем, добро пожаловать в мир рекурсии. Удачной рекурсии 😉
Следите за мной в LinkedIn и GitHub, чтобы узнать больше о Python и науке о данных.
