Contents of Recursive samples

Larry Bartholdi & his gang

July 24, 2024

This is the only true definition of factorial over $\cal {Z}$ . Note +(fact -1)+ is Γ(0), and Γ(0)⋅ 0 must be Γ(1) or 1, so +(fact -1)+ is ∞ (so is +(gamma -n)+ for integral n). (define (fact n) (if (<= n 0) (if (= n 0) 1 (/ 1 0)) (* n (fact (-1+ n)))))

This code expect is intended as a provocation... Notice the speed improvements are marginal, the arguments are not tested as cleanly as above, without memtioning poor portability (the one thing us Scheme guys should be proud of). (define fastfact (inline-lambda 1 '(pcs-code-block 0 25 () (0 12 4 ; mov.r r3, r1 2 4 1 ; mov.i r1, #1 2 8 1 ; mov.i r2, #1 83 4 8 ;@@loop:mul.r r1, r2 81 8 1 ; add.i r2, #1 0 16 8 ; mov.i r4, r2 95 16 12 ; gt.r r4, r3 34 16 241 ; jnil.s r4, @@loop 59)))) ; ret

All these examples are extracted from ``Göedel, Escher, Bach: an Eternal Golden Braid'' by Doug Hofstadter, chapter V, pages 136 ff. Their behaviour is deterministic, but can be felt as chaotic, a fact expressed by the absence of closed form and the 'ruggedness' of their graph. (define (g n) (if (= n 0) 0 (- n (g (g (-1+ n)))))) (define (h n) (if (= n 0) 0 (- n (h (h (h (-1+ n))))))) (define (female n) (if (= n 0) 1 (- n (male (female (-1+ n)))))) (define (male n) (if (= n 0) 0 (- n (female (male (-1+ n)))))) (define (q n) (if (<= n 2) 1 (+ (q (- n (q (- n 1)))) (q (- n (q (- n 2))))))) (define (fibo n) (if (<= n 2) 1 (+ (fibo (- n 1)) (fibo (- n 2)))))

Now comes a code that isn't precisely recursive. As you certainly know, +do+–loops are hanging offenses; but on the other side, PCSCHEME is kind enough to translate the loops in tail-recursive code, so... The algorithm is based on a fast series for 4 arctan(1) (see Abramowitz & Stegun, formula 4.4.42):

arctan z = $\displaystyle {\frac{{z}}{{1+z^2}}}$ $\displaystyle \big\{$ 1 + $\displaystyle {\frac{{2}}{{3}}}$ $\displaystyle {\frac{{z^2}}{{1+z^2}}}$ $\displaystyle \big[$ 1 + $\displaystyle {\frac{{4}}{{5}}}$ $\displaystyle {\frac{{z^2}}{{1+z^2}}}$ $\displaystyle \big($ 1 + … $\displaystyle \big)$ $\displaystyle \big]$ $\displaystyle \big\}$ .