Вычисление числа Фибоначчи линейной рекурсией с одним рекурсивным вызовом - Lisp

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

Помогите пожалуйста. написать на лиспе функцию fibo2, вычисляющие числа Фибоначчи линейной рекурсии с одним рекурсивным вызовом.

Решение задачи: «Вычисление числа Фибоначчи линейной рекурсией с одним рекурсивным вызовом»

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

(defun fib (n &optional (c 1) (p 0))
  (if (= n 1) c (fib (- n 1) (+ c p) c)))
 
==> FIB
 
(fib 1)
 
==> 1
 
(fib 2)
 
==> 1
 
(fib 3)
 
==> 2
 
(fib 4)
 
==> 3
 
(fib 5)
 
==> 5
 
(fib 100)
 
==> 354224848179261915075

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

В данном коде на языке Lisp определён процедурный параметр Fib, который вычисляет число Фибоначчи для заданного параметра n. Также определены два опциональных параметра: начальное значение C и промежуточное значение P. Начальное значение C по умолчанию равно 1, а промежуточное значение P по умолчанию равно 0. В данном коде реализован алгоритм вычисления чисел Фибоначчи линейной рекурсией с одним рекурсивным вызовом. Вот список описывающий работу кода:

Задано значение n = 1.
Так как условие (= n 1) истинно, то возвращается значение C = 1.
Задано значение n = 2.
Так как условие (= n 1) истинно, то возвращается значение C = 1.
Задано значение n = 3.
Так как условие (= n 1) ложно, то происходит рекурсивный вызов с параметрами (- n 1) и (+ c p) равными 2 и 1 соответственно.
Для рекурсивного вызова с параметрами (- n 1) и (+ c p) равными 2 и 1 соответственно, возвращается значение 2.
Для рекурсивного вызова с параметрами (- n 1) и (+ c p) равными 2 и 1 соответственно, возвращается значение 3.
Задано значение n = 4.
Так как условие (= n 1) ложно, то происходит рекурсивный вызов с параметрами (- n 1) и (+ c p) равными 2 и 2 соответственно.
Для рекурсивного вызова с параметрами (- n 1) и (+ c p) равными 2 и 2 соответственно, возвращается значение 3.
Для рекурсивного вызова с параметрами (- n 1) и (+ c p) равными 2 и 3 соответственно, возвращается значение 5.
Задано значение n = 5.
Так как условие (= n 1) ложно, то происходит рекурсивный вызов с параметрами (- n 1) и (+ c p) равными 2 и 3 соответственно.
Для рекурсивного вызова с параметрами (- n 1) и (+ c p) равными 2 и 3 соответственно, возвращается значение 5.
Для рекурсивного вызова с параметрами (- n 1) и (+ c p) равными 2 и 5 соответственно, возвращается значение 7.
Для рекурсивного вызова с параметрами (- n 1) и (+ c p) равными 2 и 5 соответственно, возвращается значение 12.
Задано значение n = 100.
Так как условие (= n 1) ложно, то происходит рекурсивный вызов с параметрами (- n 1) и (+ c p) равными 2 и 100 соответственно.
Для рекурсивного вызова с параметрами (- n 1) и (+ c p) равными 2 и 100 соответственно, возвращается значение 354224848179261915075.