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]