Thread: Recursion problem

I need some direction to the recursion problem listed below : recursion is a topic which i recently studied and i have not get a hang of it.

Consider the following recursive recursive function A(m,n)

A(0,n) = n+1 n greater or equal to 0
A(m,0) = A(m-1,1) m > 0
A(m,n) = A(m-1,A(m,n-1)), m>0,n>0

Find A(2,n) for n greater or equal to 0

I am not sure whether this is the right approach but here is what i did.

A(2,n) = A(1,A(2,n-1))
= A(0,A(1,A(2,A(2,n-2)))

Then i got stuck

Originally Posted by tester85

I need some direction to the recursion problem listed below : recursion is a topic which i recently studied and i have not get a hang of it.

Consider the following recursive recursive function A(m,n)

A(0,n) = n+1 n greater or equal to 0
A(m,0) = A(m-1,1) m > 0
A(m,n) = A(m-1,A(m,n-1)), m>0,n>0

Find A(2,n) for n greater or equal to 0

I am not sure whether this is the right approach but here is what i did.

A(2,n) = A(1,A(2,n-1))
= A(0,A(1,A(2,A(2,n-2)))

Then i got stuck

Two hints:

1) this is the Ackermann function

2) try first to get a non-recursive expression for A(1, n), then go on to solve A(2, n).

Ok i will try now. I tired to solve for A(1,n)

Here is what i got.

A(1,n) = A(0,A(1,n-1))
= A(0,A(0,A(1,n-2)))

it seems like an endless loop is my approach wrong. I cannot go further even with the following link.

http://en.wikipedia.org/wiki/Ackermann_function

Originally Posted by tester85

Ok i will try now. I tired to solve for A(1,n)

Here is what i got.

A(1,n) = A(0,A(1,n-1))
= A(0,A(0,A(1,n-2)))

it seems like an endless loop is my approach wrong. I cannot go further even with the following link.

First of all, A(0, A(1,n-1)) = A(1,n-1) + 1 from the definition of the function.

Let's write for A(1, n). Then you have a recurrence relation




You can calculate a number of the terms, see what formula you likely get for , and prove it by induction.

There are general theorems for solving such a recurrence relation, but they're too tedious to use for this exercise.

Ok noted with thanks. Now i know how to approach the problem.

Mistake spotted. Problem solved.