FALSE [IF] Examples of Recursion (both good and bad) --------------------------------------------------- (c) Copyright 1999 Julian V. Noble. Permission is granted by the author to use this software for any application pro- vided this copyright notice is preserved. --------------------------------------------------- 1. Euclid's algorithm for greatest common divisor (good): gcd(m,n) = gcd(n, m mod n) , n > 0 = m , n = 0 2. Fibonacci series (bad) F(n+1) = F(n) + F(n-1) , F(0) = 0, F(1) = 1 3. String reversal (bad) add first letter to end of reversal of letters 2-n: in BASIC, FUNCTION rev\$ (a\$) c\$ = MID\$(a\$, 1, 1) IF c\$ = "" THEN rev\$ = "" ELSE rev\$ = rev\$(MID\$(a\$, 2)) + c\$ END IF END FUNCTION 4. Raising a fp number to an integer power (good) x^n = (x^2)^[n/2] * x^(n mod 2) [THEN] MARKER -recurses : gcd ( m n -- gcd) ?DUP 0> IF TUCK MOD RECURSE THEN ; : fib ( n -- F[n]) DUP 0> NOT IF DROP 0 EXIT THEN DUP 1 = IF EXIT THEN 1- DUP 1- RECURSE SWAP RECURSE + ; : \$! ( src dest -- ) OVER C@ 1+ CMOVE ; : \$+ ( \$1 \$2 --) \ string concatenation: \$1 <- \$1 + \$2 OVER COUNT ( \$1 \$2 \$1+1 n1 ) DUP >R + ( \$1 \$2 dst ) OVER COUNT ( \$1 \$2 dst src n2) ROT SWAP CMOVE ( \$1 \$2) \ move chars C@ R> + SWAP C! ; \ adjust length \ CREATE pad2 256 ALLOT \ : rev\$ ( \$adr --) \ DUP C@ 0= IF DROP EXIT THEN \ empty \$ \ DUP C@ 1 = IF DROP EXIT THEN \ 1-char \$ : f^2 FDUP F* ; : f^n ( n --) ( f: x -- x^n) \ recursive ?DUP 0= IF FDROP 1e0 EXIT THEN DUP 1 AND IF FDUP ELSE 1e0 FSWAP THEN 2/ f^2 RECURSE F* ; FALSE [IF] : f^n ( n --) ( f: x -- x^n ) \ non-recursive 1e0 FSWAP BEGIN DUP 0> WHILE DUP 1 AND IF FSWAP FOVER F* FSWAP THEN 2/ f^2 REPEAT FDROP DROP ; \ Note: this algorithm beats x^n = exp( n*log(x) ) \ for integer n < 50 [THEN]