An infinite sequence is often represented in Scheme as a procedure that takes a positive integer as argument and returns the term in the specified position. As an example, here is a definition of the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, ... (in which each term after the second is the sum of the preceding two):
This is a translation into Scheme of the mathematician's recursive definition:(define fibonacci (lambda (n) (case n ((1 2) 1) (else (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))))
However, the proliferation of recursive calls makes this an extremely inefficient way of computing any but the first few terms of the sequence. The following algorithm, more nearly iterative in spirit, is faster:f(n) = 1 if n = 1 or n = 2, f(n) = f(n - 1) + f(n - 2) otherwise.
(define fibonacci (lambda (n) (let loop ((index 1) (previous 0) (current 1)) (if (= index n) current (loop (+ index 1) current (+ previous current)))))
This document is available on the World Wide Web as
John David Stone (email@example.com)