Ackermann function: Difference between revisions
(Created based on request) |
(SNUSP!) |
||
Line 20: | Line 20: | ||
return null; |
return null; |
||
}</java> |
}</java> |
||
=={{header|SNUSP}}== |
|||
/==!/==atoi=@@@-@-----# |
|||
| | Ackermann function |
|||
| | /=========\!==\!====\ recursion: |
|||
$,@/>,@/==ack=!\?\<+# | | | A(0,j) -> j+1 |
|||
j i \<?\+>-@/# | | A(i,0) -> A(i-1,1) |
|||
\@\>@\->@/@\<-@/# A(i,j) -> A(i-1,A(i,j-1)) |
|||
| | | |
|||
# # | | | /+<<<-\ |
|||
/-<<+>>\!=/ \=====|==!/========?\>>>=?/<<# |
|||
? ? | \<<<+>+>>-/ |
|||
\>>+<<-/!==========/ |
|||
# # |
Revision as of 22:54, 23 September 2008
You are encouraged to solve this task according to the task description, using any language you may know.
The Ackermann function is a classic recursive example in computer science. It is a function that grows very quickly (in its value and in the size of its call tree). It is defined as follows:
n+1 if m=0 A(m, n) = A(m-1, 1) if m>0 and n=0 A(m-1, A(m,n-1)) if m>0 and n>0
Its arguments are never negative and it always terminates. Write a function which returns the value of A(m, n). Arbitrary precision is preferred (since the funciton grows so quickly), but not required.
Java
<java>public static BigInteger ack(BigInteger m, BigInteger n){ if(m.equals(BigInteger.ZERO)) return n.add(BigInteger.ONE);
if(m.compareTo(BigInteger.ZERO) > 0 && n.equals(BigInteger.ZERO)) return ack(m.subtract(BigInteger.ONE), BigInteger.ONE);
if(m.compareTo(BigInteger.ZERO) > 0 && n.compareTo(BigInteger.ZERO) > 0) return ack(m.subtract(BigInteger.ONE), ack(m, n.subtract(BigInteger.ONE)));
return null; }</java>
SNUSP
/==!/==atoi=@@@-@-----# | | Ackermann function | | /=========\!==\!====\ recursion: $,@/>,@/==ack=!\?\<+# | | | A(0,j) -> j+1 j i \<?\+>-@/# | | A(i,0) -> A(i-1,1) \@\>@\->@/@\<-@/# A(i,j) -> A(i-1,A(i,j-1)) | | | # # | | | /+<<<-\ /-<<+>>\!=/ \=====|==!/========?\>>>=?/<<# ? ? | \<<<+>+>>-/ \>>+<<-/!==========/ # #