Converting a recursion to a loop

[japplepie]

public static int function(int n, int a, int b){
if (n>0){
if(b==0)
return a;
else
return function(n-1,a,function(n,a,b-1));
}
return b;
}

I have a recursive function of this form, how do I convert it to a loop?

 

[Mark44]

Put [ code ] and [ /code ] tags (without spaces) around your code to preserve your indentation. I have done this in your code below.

public static int function(int n, int a, int b){
	if (n>0){
		if(b==0)
			return a;
		else
			return function(n-1,a,function(n,a,b-1));
	}
	return b;
}

I have a recursive function of this form, how do I convert it to a loop?

First, figure out what the recursive function does, then reproduce that action in a loop.

 

[japplepie]

I know what it does and I know how it does it, but I couldn't think of it as a loop.
If it helps here's the real code.

public class hyperoperations {
	
	public static int baseElement(int n, int a){
		if (n==0)//successorship case (do nothing & retrieve the 1st parameter)
			return a;
		else if (n==1)//addition case (addition depends on iteration of incrementing with a constant)
			return 0;
		else if (n>1)//multiplication and higher case (anything higher than addition depends on iteration of operations depending on the 1st parameter itself)
			return 1;
		return -1;
	}
	
	public static int operation(int n, int a, int b){
		if (n==0){//successorship case (increment the 2nd parameter by 1)
			return b+1;
		}
		else if (n>0){//addition and higher case
			if(b==0)
				return baseElement(n-1,a);//get the base element or the zero element of the preceding order of n
			else
				return operation(n-1,a,operation(n,a,b-1));//expand until the 2nd parameter equals zero while considering right associativity
		}
		return -1;	
	}

    public static void main (String[] args){//negative value means undefined (for the domain of non-negative a,b,n)
    	System.out.println("Format : input_a <operation_magnitude_n> input_b = output_c");
    	System.out.println("5<1>2="+operation(1,5,2));
    	System.out.println("5<2>2="+operation(2,5,2));
    	System.out.println("5<3>2="+operation(3,5,2));
    	System.out.println("5<4>2="+operation(4,5,2));
    }	
}

//Notes:
//operation n=1 = addition (a+b)	(a+b = a+1+1+... b many times)
//operation n=2 = multiplication 	(a*b = a+a+... b many times)
//operation n=3 = exponentiation 	(a^b = a*a*... b many times) 
//operation n=4 = tetration 		(a^^b = a^a^... b many times)
//operation n=k = k-tion
//always assumes right associativity e.g. 3<4>3 = 3^(3^(3)) != 3^3^3 <-- 3^27 != 3^9

 

[AlephZero]

If the last statement in the routine calls the function recursively just once, you can eliminate the recursion like this:
http://blogs.msdn.com/b/chrsmith/archive/2008/08/07/understanding-tail-recursion.aspx
http://en.wikipedia.org/wiki/Tail_call

But your function makes two recursive calls each time it is executed, not one. So you need some way to remember and restore the arguments to the calls. With your recursive code, the function call stack does that for you automatically, of course.

 

[harborsparrow]

It is a very good exercise to take the most trivial recursive function you can find and rewrite it non-recursively, because doing so will make you, finally once and for all, understand what is happening in memory during recursion. You'll need to use an array of arrays. Each recursive call stores copies of its local variables on the call stack. Without recursive calls, you need a loop, with pointers into the array of arrays, where you store the same information (but do all the work yourself). So you are just looping, and stashing information in the array of arrays, and keeping your own pointers. This is a mechanical way to implement a recursive algorithm completely under YOUR control, but the algorithm is still recursive.

By "pointer", in the above paragraph, I just mean an index into the array.

If you walk thru three stages of a factorial call by hand, you'll see what I mean.

For some problems, however, you may be able to find a non-recursive algorithm to use instead.