Простая рекурсия

Рекурсия — это мощная концепция в Scheme, где функция вызывает саму себя для решения более мелких подзадач исходной задачи. Шаблон простой рекурсии включает базовый вариант для остановки рекурсии и рекурсивный вариант для уменьшения проблемы.

Общая структура рекурсивной функции выглядит следующим образом:

(define (function-name args)
  (if (base-condition)
    base-result
    (recursive-call)))

• Базовое условие: останавливает рекурсию.
• Базовый результат: значение, возвращаемое при выполнении базового условия.
• Рекурсивный вызов: вызов самой функции с измененными аргументами, которые приближают вычисления к базовому случаю.

Пример: сумма чисел (от 1 до n)

Простая рекурсивная функция для вычисления суммы чисел от 1 до n:

(define (sum-to-n n)
  (if (= n 0)                  ; Base case: stop when n is 0
    0                          ; Base result: sum is 0
    (+ n (sum-to-n (- n 1))))) ; Recursive call: sum current n with result of smaller problem

Как это работает: разборка и сборка

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

Пошаговая трассировка суммы до n 3

1. Первоначальный вызов: сумма-n 3 → (+ 3 (сумма до n 2))

2. Второй вызов: сумма к n 2 → (+ 2 (сумма до n 1))

3. Третий вызов: сумма к n 1 → (+ 1 (сумма до n 0))

4. Базовый случай: сумма к n 0 → 0

Собираем окончательный результат

После решения простейшего случая каждый уровень вычислений завершается:

1. сумма до n 0 дает 0
2. сумма до n 1 становится (+ 1 0) = 1
3. сумма до n 2 становится (+ 2 1) = 3
4. сумма до n 3 становится (+ 3 3) = 6

Пример: печать каждого элемента списка

Вот простая рекурсивная функция для печати каждого элемента списка:

(define (print-elements lst)
  (if (null? lst)
    (lumi-message "done")
    (begin
      (lumi-message (number->string (car lst))) ; Print the first element
      (print-elements (cdr lst)))))             ; Process the rest of the list

• Базовый случай: Если список пуст (null? lst), остановить рекурсию.
• Рекурсивный случай: Распечатайте первый элемент (car lst), затем вызовите функцию для остальной части списка (cdr lst).

Пример использования

(print-elements (list 1 2 3))

Выход:

• “1”
• “2”
• “3”

Результат: “готово”

Как это работает

1. Функция извлекает первый элемент списка, используя car, и обрабатывает его.
2. Затем он вызывает себя с остальной частью списка (cdr).
3. Этот процесс повторяется до тех пор, пока список не станет пустым (null? lst).

Резюме

• Простая рекурсия состоит из:
  1. Базовый случай: останавливает рекурсию.
  2. Рекурсивный случай: сводит проблему к базовому случаю.
• Каждый рекурсивный вызов приближает вычисление к завершению.
• После достижения базового случая результаты объединяются по завершении рекурсии.

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