government / testdata / recursion.gov.lisp

@ da006f04d8870dcf444b3b0380729d78f076b2ea | history


; A define can see itself, so functions can recurse.
(define fact (lambda (n) (if (== n 0) 1 (* n (fact (- n 1))))))
(fact 10)             ;=> 3628800

(define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
(fib 20)              ;=> 6765

; Calls in tail position do not grow the stack.
(define count (lambda (n) (if (== n 0) 'done (count (- n 1)))))
(count 1000000)       ;=> done

(define sum (lambda (n acc) (if (== n 0) acc (sum (- n 1) (+ acc n)))))
(sum 100000 0)        ;=> 5000050000

(define reverse (lambda (l acc) (if (== l ()) acc (reverse (cdr l) (cons (car l) acc)))))
(reverse '(1 2 3) ()) ;=> (3 2 1)

; Mutual recursion is impossible: odd? does not exist when even? is defined.
(define even? (lambda (n) (if (== n 0) T (odd? (- n 1)))))
(define odd? (lambda (n) (if (== n 0) F (even? (- n 1)))))
(even? 4)             ;=! no statute for symbol odd?

(define y (+ y 1))    ;=! used before its definition is complete