Задачка: A(4,3)

функция A(x,y) определена как
A(0,y) = 1, y ≥ 0
A(1,0) = 2
A(x,0) = x + 2, x ≥ 2
A(x + 1, y + 1) = A( A(x, y + 1), y), x ≥ 0, y ≥ 0

A(4,3) = ?

Данная функция есть функция Аккермана - простой пример вычислимой функции, которая не является примитивно рекурсивной.

F(z) = A(4, z)

Попытки вычислить A(4, 3) в лоб обречены на провал (код на clojure):

(defn A([x y]
 (cond 
  (zero? x) 1
  (and (= x 1) (zero? y)) 2
  (and (>= x 2) (zero? y)) (+ x 2)
  :else (recur (A (dec x) y) (dec y))
 )
))

Однако, на erlang прямо в лоб решается запросто:

-module(ack).
-export([a/2]).

a(0,_) -> 1;
a(1,0) -> 2; 
a(X,0) -> X+2;
a(X,Y) -> a( a(X-1,Y), Y-1).

запускаем...

$ erl
1> c(ack.erl).
{ok,ack}
2> ack:a(4,3).
ответ скрыт

Решить данную задачу на clojure вполне реально - дерзайте!

Level 1

ps. Я тем временем заработал Level 1 на Project Euler - на мой взгляд, отличный способ прокачать навыки в функциональном программировании.