В какой-то момент своей зарождающейся карьеры программиста вы, вероятно, слышали, как дрожащий голос в своей голове ставил этот пугающий вопрос:
«Нужно ли мне решать эту проблему рекурсивно?»
Внезапно вы стоите на краю, казалось бы, бесконечной пропасти, дно которой, кажется, хранит только одну уверенность - неопределенность. Но почему даже мысль о рекурсии вызывает у многих из нас такое рефлексивное чувство страха?
Это могло быть связано с тем, что большинство программистов занялись более процедурным или объектно-ориентированным программированием. Таким образом, мы придерживаемся более итеративных подходов, таких как циклы, и избегаем рекурсии из-за незнания функционального программирования в целом. Кроме того, итерация обеспечивает конкретность - вы можете визуализировать и иногда подсчитать, сколько раз будет запускаться ваша программа. Для многих из нас такая конечность обеспечивает безопасность, комфорт и предсказуемость.
Однако мы сталкиваемся с проблемами, которые ставят под сомнение нашу склонность к конечности и кратковременной памяти. Например, предположим, что вы хотите пройти через древовидную структуру данных, подобную приведенной ниже - представьте, что это конкретное дерево простирается намного ниже, чем показано.
Итерационные подходы с зацикливанием требуют определенной степени уверенности в отношении размера или глубины такого дерева. С каждым дочерним узлом, ведущим к большему количеству дочерних узлов, которые затем приводят к своим собственным дочерним узлам ... вы можете видеть, как каждая «итерация» увеличивается в сложности. Попытки создать конечные границы для вашей логики обхода неизменно приводят к очень конкретным мигрени.
Рекурсия обеспечивает элегантное (но пугающее) решение этого типа «фрактальной проблемы» - большой проблемы, которая в конечном итоге состоит из множества меньших версий этой исходной проблемы.