В этой статье вы узнаете о рекурсии и о том, как она работает.

Примеры в этой статье на языке Go, но концепция рекурсии одинакова для любого языка программирования.

Что такое рекурсия?

В большинстве языков программирования функция может вызывать другую функцию. Но функция также может вызывать саму себя. Рекурсия - это техника, при которой функция вызывает саму себя.

Пример:

// Функция для вычисления факториала с использованием рекурсии
func factorial(n int) int {
	if n == 0 { // Базовый случай: факториал 0 равен 1
		return 1
	}
	return n * factorial(n-1) // Рекурсивный вызов
}

Здесь функция вызывает сама себя, что называется рекурсией.

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

Аналогия рекурсии в реальной жизни

Давайте разберемся, как на самом деле работает рекурсия, с помощью примера.

Представьте, что вы стоите в очереди в магазине и не знаете, сколько человек впереди вас.

Чтобы узнать это, вы спрашиваете у человека, стоящего перед вами.

Тот тоже не знает, поэтому спрашивает у того, кто стоит перед ним.

Этот процесс продолжается до тех пор, пока вопрос не дойдет до человека, стоящего в самом конце очереди, который видит, что перед ним никого нет, и отвечает, что перед ним ноль человек.

Затем ответы начинают распространяться по всей очереди. Каждый человек прибавляет единицу к названному ему числу, и передает информацию обратно.

Когда человек, стоящий впереди, отвечает: «Впереди 0 человек», следующий человек добавляет единицу и отвечает: «Впереди 1 человек» и так далее.

Все знают, сколько человек стоит перед ними в очереди.

К тому времени, когда ответ дойдет до человека, стоящего непосредственно перед вами, он добавит еще один и скажет вам. Таким образом, вы можете определить свое место в очереди, просто прибавив 1 к числу, которое назвал человек перед вами.

Этот пример иллюстрирует, как рекурсия разбивает задачу на более мелкие подзадачи, а затем объединяет их решения для решения исходной задачи.

Каждый человек в очереди представляет собой меньший экземпляр одной и той же задачи: определение количества людей впереди. Решив эти маленькие задачи и объединив их результаты, можно решить общую проблему. Именно так работает рекурсия.

Технические детали рекурсии

Наиболее важные вещи, которые необходимо учитывать при кодировании рекурсии, - это выяснить:

Рекурсионный случай: Минимальная работа, которую мы можем выполнить. В приведенном выше примере спросить у человека, стоящего перед вами, сколько человек находится впереди него, - это наименьший объем работы, который мы можем выполнить.

Базовый случай: Состояние, при котором не требуется никакой работы. В приведенном выше примере человеку, стоящему впереди очереди, не нужно ничего спрашивать, поэтому это условие, при котором не требуется никакой работы.

Простой пример рекурсии

Вычисление факториала - это простейший пример рекурсии, который поможет понять, как она работает.

Существует множество способов вычислить факториал числа. Но здесь мы рассмотрим рекурсивный способ его нахождения.

Прежде чем думать о том, как это сделать, нам нужно знать, что такое факториал числа.

Факториал числа - это умножение всех чисел от 1 до этого числа.

Например, факториал числа 5 равен 120 - это 5×4×3×2×1.

Математически это можно представить следующим образом:

Это означает, что если мы знаем значение числа (5-1)!, то можем легко получить факториал, просто умножив 5 на него.

Вот как мы находим факториалы 4, 3, 2, 1 и 0:

Факториал 4 = 4×(4-1)!
Факториал 3 = 3×(3-1)!
Факториал 2 = 2×(2-1)!
Факториал 1 = 1
Факториал 0 = 1

Из этого видно, что для нахождения факториала 5 нужно умножить 5 на 4!

Более общий пример

Чтобы найти факториал числа n, нужно умножить n на (n-1)! Это нужно делать рекурсивно.

Теперь для рекурсии должно быть условие остановки. Условие остановки - это момент, когда мы больше не выполняем никаких операций. Когда n равно 1 или n равно 0, мы можем просто остановить рекурсию, так как эти значения имеют известные факториалы. Мы можем просто сказать, что факториал 1 равен 1, и то же самое верно для 0.

Таким образом, минимальный объем работы, который нам нужно проделать, чтобы найти факториал n, составляет n×(n-1)! И мы можем прекратить выполнять над ним операции, когда найдем факториал 1 или 0.

Давайте посмотрим, как это выглядит в коде:

package main

import (
	"fmt"
)

// fact рекурсивно вычисляет факториал числа n.
func fact(n int) int {
	// базовый случай: факториал 0 или 1 равен 1
	if n == 0 || n == 1 {
		return 1
	}
	// рекурсивный случай
	return n * fact(n-1)
}

func main() {
	n := 5

	// Вычисление факториала
	factorial := fact(n)
	fmt.Println(factorial)
}

Вывод: 120

Давайте посмотрим, как это работает:

При первом вызове функции вычисляется факториал 5. Затем во втором вызове вычисляется факториал 4, и так далее, пока не будет вычислен факториал 2.

Рекурсивное вычисление факториала числа 5

При вызове факториала 2 мы получаем 2 × fact(2-1), что равно 2 × fact(1).

Это совпадает с нашим базовым случаем. Поэтому рекурсия останавливается, и 2 × fact(1) возвращает 2×1 предыдущему вызову функции, а результат помещается в стек.

Четвертый вызов функции возвращает 2 предыдущему вызову функции и поднимается из стека

Аналогично, вычисляется все остальное:

Четвертый вызов функции возвращает 2 предыдущему вызову функции и удаляется из стека.

Аналогично, вот как оценивается все остальное:

3-й вызов функции возвращает 6 предыдущему вызову функции и поднимается из стека.

Второй вызов функции возвращает 24 предыдущему вызову функции и поднимается из стека.

Первый вызов функции возвращает начальному вызову функции значение 120 и поднимается из стека.

Таким образом, функция возвращает значение 120 первоначальному вызову функции.

Зачем нам нужен базовый вариант?

В приведенном выше примере мы использовали условие остановки для кода. Но что, если мы не добавим условие остановки или если написанная нами функция никогда не выполнит условие остановки?

Будет ли код работать вечно?

Нет - даже если вы не прерветесь, ваш код не будет работать вечно. Давайте разберемся, почему это так, с помощью примера.

package main

import "fmt"

func printFive() {
    fmt.Println(5) // Печатает число 5

    // Вызов себя рекурсивно
    printFive()
}

func main() {
    printFive() // Начальный вызов для запуска рекурсии
}

На выходе:

5
5
5
5
5
5
5
5 ...

fatal error: stack overflow

Если вы запустите приведенный выше код, то увидите, что функция не выполняется вечно и завершается сообщением: fatal error: stack overflow.

Когда функция вызывается, она сохраняется в стеке вызовов. Вот как функция print_five() хранится в стеке вызовов, когда она вызывается в первый раз.

Вызов стека при первом вызове функции

Функция вызывает себя снова и снова, и при каждом вызове она сохраняется в стеке вызовов.

Стек вызовов после n вызовов функций

Но стек вызовов имеет ограниченный размер и не может хранить неограниченное количество функций.

Когда стек переполнен, он не может вместить больше вызовов, что приводит к ошибке переполнения стека.

Поэтому базовый пример очень важен для предотвращения подобных ошибок и обеспечения правильного завершения рекурсии.

Теперь давайте рассмотрим другой пример, чтобы еще лучше понять рекурсию.

Как проверить, является ли слово палиндромом?

Прежде чем мы погрузимся в код, вы должны знать, что такое палиндром. Палиндром - это слово или несколько слов, которое читается одинаково как в прямом, так и в обратном направлении.

Например, "город дорог" читается одинаково как вперед, так и назад.

Чтобы проверить, является ли слово палиндромом, нужно проверить, совпадают ли первая и последняя буквы. Если да, то нужно проверить, одинаковы ли вторая и предпоследняя буквы.

В "город дорог" первая и последняя буквы одинаковы, поэтому мы проверяем, одинаковы ли вторая и предпоследняя буквы. Так и есть, теперь проверяем, одинаковы ли третья и предпоследняя буквы. Теперь осталось проверить только одну букву. Одна буква всегда является палиндромом, потому что читается одинаково в обоих случаях.

Проверяем "город дорог" палиндромом

Итак, теперь попробуем подумать об этом рекурсивно, что предполагает минимальное количество работы и определение момента, когда работа не требуется.

Минимальный работы

Проверяем, совпадают ли первая и последняя буквы, и если да, то удаляем первую и последнюю буквы из слова.

Работа не требуется

Если в нем осталась одна буква или вообще нет букв, мы можем просто сказать, что это палиндром.

Теперь давайте посмотрим, как выглядит код:

package main

import (
	"fmt"
	"strings"
)

// checkPalindrome проверяет, является ли заданная строка палиндромом
func checkPalindrome(text string) bool {
	// Преобразуем строку в срез рун для корректной работы с Unicode
	runes := []rune(text)

	// Базовый случай: если длина текста равна 0 или 1, возврщается true
	if len(runes) == 0 || len(runes) == 1 {
		return true
	}

	// Проверяем, совпадают ли первый и последний символы
	if runes[0] == runes[len(runes)-1] {
		// Рекурсивно вызываем функцию с удалением первого и последнего символов
		return checkPalindrome(string(runes[1 : len(runes)-1]))
	}

	return false
}

func main() {
	// Убираем пробелы и приводим строку к одному регистру для корректной проверки
	text := "город дорог"
	text = strings.ReplaceAll(text, " ", "") // Убираем пробелы
	text = strings.ToLower(text)             // Приводим к нижнему регистру

	// Проверяем, является ли строка палиндромом
	isPalindrome := checkPalindrome(text)
	fmt.Println(isPalindrome) // Вывод: true
}

1. Работа с Unicode:

   • Строка преобразуется в срез рун ([]rune) для корректной обработки многобайтовых символов.

   • Это позволяет сравнивать символы независимо от их байтового представления.

2. Учет регистра и пробелов:

   • Пробелы удаляются с помощью strings.ReplaceAll.

   • Строка приводится к нижнему регистру с помощью strings.ToLower.

Когда использовать рекурсию?

Рекурсия может казаться элегантной и простой. Но для решения даже простых задач она часто требует много шагов из-за перегрузки процессора, связанной с многократным добавлением методов в стек. Поэтому прежде чем использовать ее, тщательно подумайте, подходит ли она для решения вашей задачи.

Когда код требует множества циклов и выглядит запутанным и беспорядочным, рекурсия может предложить более чистое решение. Однако ее использование зависит от конкретного кода и типа данных или структуры данных. Для таких структур данных, как деревья и графы, рекурсия может быть особенно полезна.

Несмотря на внешнюю простоту, рекурсия может быть сложна для понимания и может потребовать нескольких шагов даже для решения простых задач. Поэтому еще раз убедитесь, что вы продумали свой конкретный случай использования.

Спасибо за обратную связь! Всего доброго.