HOME | 6. Local Variables | Yet Another Scheme Tutorial | 8. Higher Order Functions | Post Messages |
Calculating factorial is often used to explain recursion.
[code 1] Function fact that calculates factorials.
(define (fact n) (if (= n 1) 1 (* n (fact (- n 1)))))(fact 5) is calculated like as follows:
(fact 5) ⇒ 5 * (fact 4) ⇒ 5 * 4 * (fact 3) ⇒ 5 * 4 * 3 * (fact 2) ⇒ 5 * 4 * 3 * 2 * (fact 1) ⇒ 5 * 4 * 3 * 2 * 1 ⇒ 5 * 4 * 3 * 2 ⇒ 5 * 4 * 6 ⇒ 5 * 24 ⇒ 120(fact 5) calls (fact 4), (fact 4) calls (fact 3), then finally (fact 1) is called. (fact 5), (fact 4) ,.., and (fact 1) are allocated at different memory spaces and (fact i) stays there until (fact (- i 1)) returns a value, which wastes the memory space and takes more calculation time because of the overhead of function call.
However, recursive functions can express repetition in a simple manner. Further as lists are defined recursively, lists and recursive functions fit together. For instance, a function that makes all list items twice is defined like as follows. The function should return an empty list if the argument is an empty list to terminate the calculation.
(define (list*2 ls) (if (null? ls) '() (cons (* 2 (car ls)) (list*2 (cdr ls)))))
[code 2] shows a tail recursive version of function fact shown in [code 1].
[code 2] fact-tail, tail recursive version of fact
(define (fact-tail n) (fact-rec n n)) (define (fact-rec n p) (if (= n 1) p (let ((m (- n 1))) (fact-rec m (* p m)))))fact-tail calculates factorial like as follows:
(fact-tail 5) ⇒ (fact-rec 5 5) ⇒ (fact-rec 4 20) ⇒ (fact-rec 3 60) ⇒ (fact-rec 2 120) ⇒ (fact-rec 1 120) ⇒ 120As fact-rec does not wait the result of other functions, it disappears from the memory space when it finishes. The calculation proceeds by changing argument of fact-rec, which is basically the same as loop. As mentioned previously, as Scheme convert a tail recursive to a loop, Scheme can do repetition without syntax for looping.
A named let is a conventional way to express loops in Scheme.
[code 3]
(define (fact-let n) (let loop((n1 n) (p n)) ; 1 (if (= n1 1) p (let ((m (- n1 1))) (loop m (* p m)))))) ; 2
[code 4]
(define (fact-letrec n)
(letrec ((iter (lambda (n1 p)
(if (= n1 1)
p
(let ((m (- n1 1)))
(iter m (* p m))))))) ; *
(iter n n)))
As shown at the line of ; *,
the local variable iter can refer itself in the definition of iter.
Syntax letrec is a conventional way to define local functions.
(do binds (predicate value)
body)
Variables are bound in the binds part, if the predicate is true, it escapes from
the loop and returns the value, otherwise the looping continues.The format of the binds part is like as follows:
[binds] → ((p1 i1 u1) (p2 i2 u2) ... )Variables p1, p2 ... are initialized with i1, i2 ... and updated with u1, u2 ... after each cycle.
[code 5] shows do version of fact.
[code 5]
(define (fact-do n) (do ((n1 n (- n1 1)) (p n (* p (- n1 1)))) ((= n1 1) p)))The variables n1 and p are initialized with n and n and subtracted by one and multiplying by (n1 - 1) after each cycle, respectively. The function returns p when n1 becomes one.
I feel do is rather complicated than named let.
Usually named let is used for simple loops. On the other hand, letrec is used for complicated recursive local functions.
I will explain higher order functions in the next chapter. Higher order functions makes your code more Scheme like.
; 1 (define (my-length ls) (if (null? ls) 0 (+ 1 (my-length (cdr ls))))) ; 2 (define (my-sum ls) (if (null? ls) 0 (+ (car ls) (my-sum (cdr ls))))) ; 3 (define (remove x ls) (if (null? ls) '() (let ((h (car ls))) ((if (eqv? x h) (lambda (y) y) (lambda (y) (cons h y))) (remove x (cdr ls)))))) ; 4 (define (position x ls) (position-aux x ls 0)) (define (position-aux x ls i) (cond ((null? ls) #f) ((eqv? x (car ls)) i) (else (position-aux x (cdr ls) (1+ i)))))
; 1 (define (my-reverse ls) (my-reverse-rec ls ())) (define (my-reverse-rec ls0 ls1) (if (null? ls0) ls1 (my-reverse-rec (cdr ls0) (cons (car ls0) ls1)))) ;------------------- ; 2 (define (my-sum-tail ls) (my-sum-rec ls 0)) (define (my-sum-rec ls n) (if (null? ls) n (my-sum-rec (cdr ls) (+ n (car ls))))) ;-------------------- ; 3 (define (my-string->integer str) (char2int (string->list str) 0)) (define (char2int ls n) (if (null? ls) n (char2int (cdr ls) (+ (- (char->integer (car ls)) 48) (* n 10)))))
; 1 (define (remove x ls) (let loop((ls0 ls) (ls1 ())) (if (null? ls0) (reverse ls1) (loop (cdr ls0) (if (eqv? x (car ls0)) ls1 (cons (car ls0) ls1)))))) ; 2 (define (position x ls) (let loop((ls0 ls) (i 0)) (cond ((null? ls0) #f) ((eqv? x (car ls0)) i) (else (loop (cdr ls0) (1+ i)))))) ; 3 (define (my-reverse-let ls) (let loop((ls0 ls) (ls1 ())) (if (null? ls0) ls1 (loop (cdr ls0) (cons (car ls0) ls1))))) ; 4 (define (my-sum-let ls) (let loop((ls0 ls) (n 0)) (if (null? ls0) n (loop (cdr ls0) (+ (car ls0) n))))) ; 5 (define (my-string->integer-let str) (let loop((ls0 (string->list str)) (n 0)) (if (null? ls0) n (loop (cdr ls0) (+ (- (char->integer (car ls0)) 48) (* n 10)))))) ; 6 (define (range n) (let loop((i 0) (ls1 ())) (if (= i n) (reverse ls1) (loop (1+ i) (cons i ls1)))))
; 1 (define (my-reverse-letrec ls) (letrec ((iter (lambda (ls0 ls1) (if (null? ls0) ls1 (iter (cdr ls0) (cons (car ls0) ls1)))))) (iter ls ()))) ; 2 (define (my-sum-letrec ls) (letrec ((iter (lambda (ls0 n) (if (null? ls0) n (iter (cdr ls0) (+ (car ls0) n)))))) (iter ls 0))) ; 3 (define (my-string->integer-letrec str) (letrec ((iter (lambda (ls0 n) (if (null? ls0) n (iter (cdr ls0) (+ (- (char->integer (car ls0)) 48) (* n 10))))))) (iter (string->list str) 0)))
; 1 (define (my-reverse-do ls) (do ((ls0 ls (cdr ls0)) (ls1 () (cons (car ls0) ls1))) ((null? ls0) ls1))) ; 2 (define (my-sum-do ls) (do ((ls0 ls (cdr ls0)) (n 0 (+ n (car ls0)))) ((null? ls0) n))) ; 3 (define (my-string->integer-do str) (do ((ls0 (string->list str) (cdr ls0)) (n 0 (+ (- (char->integer (car ls0)) 48) (* n 10)))) ((null? ls0) n)))
HOME | 6. Local Variables | Yet Another Scheme Tutorial | 8. Higher Order Functions | Post Messages |