Рекурсия

Рекурсией называется вызов функцией самой себя. Давайте рассмотрим простейший пример рекурсии:

(define (rec-fnc) (rec-fnc))
(rec-fnc)

В этом случае функция rec-fnc будет вызывать себя снова и снова, остановить её может только лишь суровое нажатие Ctrl-C.

(define (rec-fnc cnt)
 (display cnt)(newline)

 (if (not (equal? cnt 0))
  (rec-fnc (- cnt 1))
 )
 (display cnt)(newline)
)
(rec-fnc 10)

Если аргумент "cnt" передаваемый в функцию больше 0, то функция вызывет саму себя.

А в этот пример наглядно показывает как работает рекурсия:

(define (rec-fnc cnt max-cnt)
 (display (make-string cnt #\space))
 (display cnt)
 (newline)

 (if (not (equal? cnt max-cnt))
  (rec-fnc (+ cnt 1) max-cnt)
 )

 (display (make-string cnt #\space))
 (display cnt)
 (newline)
)
(rec-fnc 0 10)

Также в этом примере задаётся не только стартовое значение -- "cnt", но и конечное -- "max-cnt", по достижению которого функция перестаёт вызывать саму себя.

Хвостовая рекурсия

А в этом примере мы встречаемся с явлением переполнения стека.

(define (rec-fnc cnt max-cnt)
 ;(display (make-string cnt #\space))
 (display cnt)
 (newline)

 (if (not (equal? cnt max-cnt))
  (rec-fnc (+ cnt 1) max-cnt)
 )

 ;(display (make-string cnt #\space))
 (display cnt)
 (newline)
)
(rec-fnc 0 1000000)

Поначалу всё идёт как обычно, но по достижению некоторого уровня вложенности мы получаем ошибку:

java.lang.StackOverflowError

Но не стоит отчаиваться -- на помощь нам спешит хвостовая рекурсия:

(define (rec-fnc cnt max-cnt)
 (display cnt)
 (newline)

 (if (not (equal? cnt max-cnt))
  (rec-fnc (+ cnt 1) max-cnt)
 )
)
(rec-fnc 0 100000)

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