Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Converting a recursion to a loop

  1. May 6, 2014 #1
    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?
     
  2. jcsd
  3. May 6, 2014 #2

    Mark44

    Staff: Mentor

    Put [ code ] and [ /code ] tags (without spaces) around your code to preserve your indentation. I have done this in your code below.
    First, figure out what the recursive function does, then reproduce that action in a loop.
     
  4. May 7, 2014 #3
    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.

    Code (Text):
    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
     
  5. May 7, 2014 #4

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

  6. May 16, 2014 #5

    harborsparrow

    User Avatar
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Converting a recursion to a loop
  1. Recursion in C (Replies: 12)

Loading...