我正在尝试编写一个球拍程序，该程序计算斐波那契序列中前n项的和，而不使用递归，只使用抽象列表函数(so map、builld-list、foldr、foldl(。我可以使用助手功能。我一直纠结于如何在不使用递归的情况下列出斐波那契数。我想我可以使用lambda函数：
(lambda (lst) (+ (list-ref lst (- (length lst) 1)) (list-ref lst (- (length lst 2)))))
但我不知道如何生成输入列表/如何将其添加到函数中。一旦我有了斐波那契序列，我知道我可以用(foldl+(car-lst((cdr-lst((来求和。有人能向我解释一下如何制作斐波那契序列吗？
; This is how I figure out
#|
(1 2 3 4 (0 1))
-> (1 2 3 (1 1))
-> (1 2 (1 2))
-> (1 (2 3))
-> (3 5)
|#
(define (fib n)
(cond
[(= n 0) 0]
[(= n 1) 1]
[(> n 1)
(second
(foldr (λ (no-use ls) (list (second ls) (+ (first ls) (second ls))))
'(0 1)
(build-list (- n 1) (λ (x) x))))]))
(fib 10)
(build-list 10 fib)
升级版本2
(define (fib-v2 n)
(first
(foldr (λ (no-use ls) (list (second ls) (+ (first ls) (second ls))))
'(0 1)
(build-list n (λ (x) x)))))
(build-list 10 fib-v2)
fib-seq生成前n个斐波那契数的列表，fib-sum生成前n个斐波纳契数的和。
; Number -> [List-of Number]
(define (fib-seq n)
(cond [(= n 0) '()]
[(= n 1) '(0)]
[else (reverse
(for/fold ([lon '(1 0)]) ([_ (in-range (- n 2))])
(cons (apply + (take lon 2)) lon)))]))
; Number -> Number
(define (fib-sum n)
(if (= n 0) 0 (add1 (apply + (take (fib-seq n) (sub1 n))))))
注：fib-sum相当于以下递归版本：
(define (fib0 n)
(if (< n 2) n (+ (fib0 (- n 1)) (fib0 (- n 2)))))
(define (fib1 n)
(let loop ((cnt 0) (a 0) (b 1))
(if (= n cnt) a (loop (+ cnt 1) b (+ a b)))))
(define (fib2 n (a 0) (b 1))
(if (= n 0) 0 (if (< n 2) 1 (+ a (fib2 (- n 1) b (+ a b))))))
一旦我有了斐波那契序列，我就知道我可以用(foldl+(car-lst((cdr-lst((来求和。
请注意，您不必生成中间序列来查找和。考虑(快速(矩阵求幂解决方案：
(require math/matrix)
(define (fib3 n)
(matrix-ref (matrix-expt (matrix ([1 1] [1 0])) n) 1 0))
测试：
(require rackunit)
(check-true
(let* ([l (build-list 20 identity)]
[fl (list fib0 fib1 fib2 fib3 fib-sum)]
[ll (make-list (length fl) l)])
(andmap (λ (x) (equal? (map fib0 l) x))
(map (λ (x y) (map x y)) fl ll))))