Moving from recursive to iterative

Question

I have had a long time trying to convert this function into a loop but I can't find the way to do it. I have started with a while(m != 0) and then the conditionals inside, but the third if is the one that won't let me do it.

public static int calculatePayment(int n, int m){
    if(m == 0) return n + 1;
    if(n == 0 && m > 0) return calculatePayment(1, m - 1);
    if(n > 0 && m > 0) return calculatePayment(calculatePayment(n - 1, m), m - 1);
    return 0;
}

Also, I don't know is I need to use a BigInteger, aretrograde and inverteds the program will run StackOverFlow Error and won't let me know if I need it.

Edits:

1st:

m cannot be less than zero in the input, that will never happen. Same situation with n, the code doesn't need to handle that.

So far I have this:

while(m > 0){
             if(n == 0 && m > 0){n = 1; m--;}
             if(n > 0 && m > 0){m--; n = IDONTKNOWWHAT;}//here n is the value of
                                                        //the payment if n = n - 1
                                                        //and m = m
                                                        //here is the big deal.
            }
if(m == 0) return n + 1;   //or print

Also the code cannot be reduced to a mathematical formula, I tried.

That’s a strange “payment” algorithm. I guess the accounting is going mad… — Holger, Feb 18 '14 at 18:04
Grab pen and paper and trace the execution flow. You can derive a closed formula not involving iteration nor recursion. Given, of course, that the code calculates what you are actually looking for. — Stefano Sanfilippo, Feb 18 '14 at 18:25
I have my doubts that tracing the execution flow of a method which throws `StackOverFlowError` with pen and paper will lead to a formula. — Holger, Feb 18 '14 at 18:58
@NicolásCarlo n doesn't need to reach a value, is the function `calculatePayment(n,m)` n doesn't need to reach any value, n is the most variable. m is the one which needs to reach zero, so, then payment will be `n + 1` — Hans, Feb 18 '14 at 19:06
possible duplicate of [How to rewrite Ackermann function in non-recursive style?](http://stackoverflow.com/questions/10742322/how-to-rewrite-ackermann-function-in-non-recursive-style) — Jakub Kotowski, Feb 18 '14 at 20:57

score 2 · Accepted Answer · edited May 23 '17 at 12:20

2

It looks like you're trying to find a non-recursive algorithm for computing the Ackermann's function. I wouldn't mind having my salary computed like that:) I guess its an attempt to disguise a homework?

Anyway, you can just simulate the stack and store intermediate values and then it's quite easy, see: How to rewrite Ackermann function in non-recursive style?

By the way, Ackermann's function grows extremely fast. You could use BigInteger but it would be mostly futile anyway. Exact values of the function are known only for a couple of the smallest arguments. Also, a lot of recursion is involved so you need to cache intermediate values to postpone the StackOverflow, google about memoization.

edited May 23 '17 at 12:20

Community

1
1

answered Feb 18 '14 at 21:02

Jakub Kotowski

7,411
29
38

1

This is great!, I did'nt know the name of the function, this is great,thank you so much, and yeah, is kind of a homework, but is far beyond than this. By the way, I just need to calculate values of m < 4 and n < 200, I'll see if I have to use the BigInteger. Anyway, I'll try and let you know. – Hans Feb 18 '14 at 21:34
Caching might or mightn't help to postpone the StackOverflowError, it make even make it to come faster as it speeds up the computation. – maaartinus Feb 19 '14 at 01:06

Moving from recursive to iterative

Edits:

1st:

1 Answers1