Рекурсия — не только способ определения функций.
Термином рекурсивный (самоссылающийся) также характеризуют и процессы, и структуры данных, построенные на основе самих себя.
A(0, y) = y + 1
A(x+1, 0) = A(x, 1)
A(x+1, y+1) = A(x, A(x + 1, y))
Не является примитивно-рекурсивной, двойная рекурсия. Доказать, что принадлежит R довольно трудно.