Ряд фиббоначчи - Lisp

Формулировка задачи:

определить функцию , вычисляющую n-ый член ряда Фибоначчи: 1 1 2 3 5 8 13 21 .... . сделать рекурсией и циклом.

Решение задачи: «Ряд фиббоначчи»

Листинг программы

(defun fib (n &optional (r (list 1 0)))
  (if (zerop n) (car r) (fib (- n 1) (cons (+ (car r) (cadr r)) r))))
 
==> FIB
 
(fib 0)
 
==> 1
 
(fib 1)
 
==> 1
(fib 100)
 
==> 573147844013817084101

Объяснение кода листинга программы

В данном коде:

(defun fib (n &optional (r (list 1 0))) — это определение функции с именем fib, которая принимает один обязательный аргумент n и один необязательный аргумент r. Если аргумент r не указан, то его значение по умолчанию — это список [1, 0].
(if (zerop n) (car r) (fib (- n 1) (cons (+ (car r) (cadr r)) r)) — это тело функции. Если значение n равно нулю, то возвращается первый элемент списка r. В противном случае, вызывается рекурсивно функция fib с аргументом (- n 1) и списком, в который добавляется сумма первого и второго элементов списка r, а затем этот список передается в качестве значения r для следующего вызова функции.
(fib 0) — это вызов функции fib с аргументом 0. В соответствии с определением функции, если n равно нулю, то возвращается первый элемент списка r, то есть 1.
(fib 1) — это вызов функции fib с аргументом 1. В соответствии с определением функции, если n равно 1, то возвращается первый элемент списка r, то есть 1.
(fib 100) — это вызов функции fib с аргументом 100. В соответствии с определением функции, вызывается рекурсивно функция fib с аргументом (- n 1), то есть 99, и списком, в который добавляется сумма первого и второго элементов списка r, то есть 1 + 0 = 1. Затем этот список передается в качестве значения r для следующего вызова функции. Процесс повторяется до тех пор, пока не будет достигнуто условие завершения рекурсии (n = 0). В итоге, возвращается результат последнего вызова функции, то есть 573147844013817084101.