extra/rosetta-code/ackermann/ackermann.factor

   1 ! Copyright (c) 2012 Anonymous
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: combinators locals kernel math ;
   4 IN: rosetta-code.ackermann
   5
   6 ! http://rosettacode.org/wiki/Ackermann_function
   7
   8 ! The Ackermann function is a classic recursive example in
   9 ! computer science. It is a function that grows very quickly (in
  10 ! its value and in the size of its call tree). It is defined as
  11 ! follows:
  12
  13 ! A(m,n) = {
  14 !     n + 1             if m = 0
  15 !     A(m-1, 1)         if m > 0 and n = 0
  16 !     A(m-1, A(m, n-1)) if m > 0 and n > 0
  17 ! }
  18
  19 ! Its arguments are never negative and it always terminates.
  20 ! Write a function which returns the value of A(m,n). Arbitrary
  21 ! precision is preferred (since the function grows so quickly),
  22 ! but not required.
  23
  24 :: ackermann ( m n -- u )
  25     {
  26         { [ m 0 = ] [ n 1 + ] }
  27         { [ n 0 = ] [ m 1 - 1 ackermann ] }
  28         [ m 1 - m n 1 - ackermann ackermann ]
  29     } cond ;