CODEWITHSUNDEEP
javafunctionrecursioniteration
user3096218
user3096218

Reputation: 11

from recursion to iteration

I have recursive function:

public static int fRek(int n) {         
    if (n <= 0)
       return 1;            
    else if (n == 1) 
       return 2;       
    else
       return 3 * fRek(n-2)-3;  
}

question: how can I write it in iteration? Loops? I have this:

public static int fIter(int a) {
    int b = 1 ;
        if (a <= 0) return 1;           
        else if (a == 1) return 2;  
        for (int i = 1; i <= a; i = i+2) {            
              b = b * 3;            
              b = b - 3;        
        }        
        return b;    
    }
}

But it works for just for even numbers: a = 4,6,8,... for odd numbers it doesnt works correctly, I dont know why

Upvotes: 0

Views: 118

Answers (4)

albusshin
albusshin

Reputation: 4010

For even numbers your second algorithm wouldn't work because that in the first piece of code, the function returns 2 if n == 1 :

else if (n == 1) 
   return 2;

and in your second algorithm if the input parameter a is odd, the for loop would reduce it finally to 1 instead of 0, thus calculating using b=1 is incorrect. You should use b=2 in the case of a being odd, and use b=1 in the case of a being even.

Also, you should use the for loop from i=1 while a being odd and i=2 while a being even.

Upvotes: 1

cangrejo
cangrejo

Reputation: 2202

The reason it works for even numbers is because you are hard coding the corresponding stop condition at the beginning of your function.

Look at your recursive function. If the number is even, there will be recursive calls until n == 0; That is, until we get here:

if (n <= 0)
   return 1;

From there, we compute the final result bottom up.

return 3 * 1 -3;  //that's 0 
return 3 * 0 -3;  //that's -3
return 3 * -3 -3; //that's -12
return 3 * 3 -3;  //that's -39
//...and so on

In case the number is odd, we start from 2, because of this line:

else if (n == 1) 
   return 2;

From there, we compute the final result bottom up.

return 3 * 2 -3;  //that's 3 
return 3 * 3 -3;  //that's 6
return 3 * 6 -3;  //that's 15
return 3 * 15 -3;  //that's 42
//... and so on

Your iterative function starts like this.

int b = 1 ;

That is, you're imposing a condition that should only be there in case the number is even. Instead, you should test if the number is even or odd.

if (a % 2 == 0) 
    b = 1;           
else 
    b = 2;  
for (int i = b; i <= a; i = i+2) {    
    //...
}

Upvotes: 0

user2858650
user2858650

Reputation:

Your second problem is still trying to solve this recursively. You need to break out your logic into a While statement. Here's a start:

int tmp = n
while (tmp > 1) {

Insert main logic here

}
//Base Cases
if (tmp == 1)
    n += 3 

if (tmp <= 0)
    n += 0 //This does nothing but listing for illustration

return n;

Upvotes: 0

Ingo
Ingo

Reputation: 36339

Yes loops, though it is not so easy in this case, because the function is not tail recursive.

Let us first convert it to a tail recursive function. For this we pass an argument that notes how often the provisional result must go through the final function x => 3*x-3:

public static int fRek1(int n, int count) {
   if (n <= 0) return finalf(1, count);
   else if (n == 1) return finalf(2, count);
   else return fRek(n-2, count+1);
}
public static int fRek(int n) { return fRek1(n, 0); }
public static int finalf(int n, int count) {
    while (count > 0) {
       n = 3*n-3;
       count--;
    }
    return n;
}

Now you probably see how to convert fRek1 above to a while loop: just replace the recursion with a block where the variables n and count get their new values and enclose the method body in a while (true).

Upvotes: 0

Related Questions