MainStack - 1 year ago 87
Java Question

# recursive to iterative (java)

as a beginner in programming I am trying to convert the following recursive method to an iterative one but I just don't get the hang of it. The method or function has a binary tree like recursion and I would like to use an array for the iterative solution.. unfortunately I am very confused how to do it.

I have already checked the way of converting the fibonnaci recursive method to an iterative one. But I think this is not the same here. Also I am not sure if a tree search method is useful?! Any help, hint, idea would be appreciated. Thanks.

``````public static int funct(int n) {

if (n == 0) return 1;
if (n == 1) return 2;
if n > 1 return funct(n-2)*funct(n/2);

}
``````

Answer Source

Now the real function is without last if:

``````public static int funct(int n) {
if (n == 0) return 1;
if (n == 1) return 2;
return funct(n-2) * funct(n/2);
}
``````

As the recursive calls refer to smaller parameters one can cache all return values upto n.

Unfortunately this already spoils the pleasure, as the resulting code is complete:

``````public static int funct(int n) {
int[] results = new int[n+1];
results[0] = 1;
results[1] = 2;
int i = 2;
while (i <= n) {
results[i] = results[i-2] * results[i/2];
++i;
}
return results[n];
}
``````

It indeed looks like fibonacci.

In general one would not need to fill all items of `results`. like probably `results[n - 1]`. Unfortunately you should have learnt prior to this problem:

• Solving tail recursion.
• Using a stack (like here) to use inner results of a recurive call.

You might look into those topics.

Math afterlude

The initial values are powers of 2. As the result is a product of earlier results, all results will be powers of 2.

``````f(0) = 1 = 2^0
f(1) = 2 = 2^1
f(n) = f(n - 2) * f(n / 2)
``````

Hence you can introduce:

``````g(0) = 0
g(1) = 1
g(n) = g(n - 2) + g(n / 2)
f(n) = 2^g(n)
``````

This will enlarge the range you can calculate as say 2100.

You will also see:

``````g(2k + 1) = g(2k) + 1
``````

So you will only need a domain of even numbers:

``````g(2k) = g(2(k-1)) + g(k - k%2) + k%2
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download