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
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
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.