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
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.
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).
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; 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) { //... } 