MainStack - 1 month ago 5x

Java Question

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

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 **2 ^{100}**.

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
```

Source (Stackoverflow)

Comments