MainStack 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];
    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