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

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

Загальна структура рекурсивної функції виглядає так:

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

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

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

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

(define (sum-to-n n)
  (if (= n 0)                  ; Базовий випадок: зупинитися, коли n дорівнює 0
    0                          ; Базовий результат: сума дорівнює 0
    (+ n (sum-to-n (- n 1))))) ; Рекурсивний виклик: додати n до результату меншої задачі

Як це працює: розбирання та повторне збирання

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

Покрокове трасування sum-to-n 3

1. Початковий виклик: sum-to-n 3 → (+ 3 (sum-to-n 2))

2. Другий виклик: sum-to-n 2 → (+ 2 (sum-to-n 1))

3. Третій виклик: sum-to-n 1 → (+ 1 (sum-to-n 0))

4. Базовий випадок: sum-to-n 0 → 0

Повторне складання кінцевого результату

Коли найпростіший випадок розв’язано, кожен шар обчислення завершується:

1. sum-to-n 0 дає 0
2. sum-to-n 1 стає (+ 1 0) = 1
3. sum-to-n 2 стає (+ 2 1) = 3
4. sum-to-n 3 стає (+ 3 3) = 6

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

Ось проста рекурсивна функція для друку кожного елемента в списку:

(define (print-elements lst)
  (if (null? lst)
    (lumi-message "done")
    (begin
      (lumi-message (number->string (car lst))) ; Вивести перший елемент
      (print-elements (cdr lst)))))             ; Обробити решту списку

• Базовий випадок: якщо список порожній (null? lst), зупинити рекурсію.
• Рекурсивний випадок: вивести перший елемент (car lst), потім викликати функцію для решти списку (cdr lst).

Приклад використання

(print-elements (list 1 2 3))

Вивід:

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

Результат: “done”

Як це працює

1. Функція отримує перший елемент списку за допомогою car і обробляє його.
2. Потім вона викликає себе з рештою списку (cdr).
3. Цей процес повторюється, доки список не стане порожнім (null? lst).

Резюме

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

Рекурсія відображає структуру задачі та забезпечує чіткий, логічний потік. Завжди передбачайте базовий випадок, щоб уникнути нескінченної рекурсії.