Рекурсия и зацикливание

Факториал

В элементарной арифметике очень часто встречается операция “факториал”: факториалом числа N называется произведение всех целых чисел от 1 до N включительно. На языке Scheme это определение выглядит так:

(define (factorial n)
  (if (> n 0)
    (* n (factorial (- n 1)))
    1))

Процесс вычисления результата этой операции можно проиллюстрировать следующей последовательностью выражений:

(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (factorial 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120

Определение операции, которое использует определяемую операцию, называется рекуррентным или рекурсивным. Встречаются и взаимно рекурсивные определения, например:

(define (чётное? x) 
  (if (= x 0) #t (нечётное? (- x 1))))

(define (нечётное? x) 
  (if (= x 0) #f (чётное? (- x 1))))

Ключевым моментом при написании рекурсивных определений является условие остановки: почти всегда рекурсивное определение имеет вид

(define (нечто ...)
  (if условие рекурсивная-часть нерекурсивная-часть))

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

Сложные условия

В прошлой главе в одном из упражнений предлагалось реализовать отрицание, конъюнкцию и дизъюнкцию. Вообще говоря, эти операции встроены в язык Scheme: называются они not, and и or. Более того, конъюнкция и дизъюнкция являются специальными формами: их входы вычисляются слева направо до тех пор, пока они могут повлиять на итоговый результат. А именно: аргументы and вычисляются до первого встреченного #f, а аргументы or – до первого встреченного #t.

(and #f (display "Это не будет напечатано"))
(or #f #f (display "Это будет напечатано"))

Также часто встречается специальная форма cond, имеющая вид

(cond
  (условие_1 выражение_1)
  (условие_2 выражение_2)
  ...
  (условие_n выражение_n)
)

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

(define (factorial n)
  (cond
    [(> n 0) (* n (factorial (- n 1)))]
    [#t      1]))

Циклы (хвостовая рекурсия)

Существенным недостатком описанного выше способа вычисления факториала является расход памяти: выражение вида

(factorial N)

в процессе вычисления разворачивается в выражение

(* N ... (* 2 (* 1 (factorial 0)))..)

длина которого пропорциональна N.

Альтернативный, более эффективный, способ вычисления таков:

(define (factorial n)
  (define (factorial-loop result k)
    (if (> k n) 
      result
      (factorial-loop (* result k) (+ k 1))))
  
  (factorial-loop 1 1))

Процесс вычисления выражения

(factorial 5)

может быть проиллюстрирован следующей последовательностью:

(factorial 5)
(factorial-loop 1 1)
(factorial-loop 1 2)
(factorial-loop 2 3)
(factorial-loop 6 4)
(factorial-loop 24 5)
(factorial-loop 120 6)
120

Здесь оба “входа” вспомогательной операции factorial-loop были использованы для хранения промежуточных результатов вычисления. Как видно из иллюстрации, расход памяти не зависит от величины входных данных (если говорить совсем строго, то в реализациях языка, поддерживающих арифметику целых чисел произвольной длины, вычисление факториала числа N требует количество памяти, пропорциональное N, для хранения самого факториала).

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

Упражнения

Реализуйте операцию сумма, для которой (сумма N) – сумма всех целых чисел от 1 до N включительно.

;

Реализуйте операцию сумма-цифр, вычисляющую сумму цифр поданного на вход числа.

;

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

;

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

;

Реализуйте операцию НОД, вычисляющую наибольший общий делитель поданных на вход целых чисел. Считать, что (НОД 0 0) равен 0. Вам может пригодиться Алгоритм Евклида.

;