Razorbolt February 2016
### StackOverflow error while using recursion

I am trying to get the number (n) to (m) and to me the algorithm makes sense yet it always crashes with a Stackoverflow error. any help? here's my code:

```
private static int solve(int n, int m, int steps) {
if (n > m || n <= 0) {
//--steps;
return 0;
} else if (n == m)
return steps;
return Math.min(solve(n * 2, m, steps++), solve(n - 1, m, steps++));
}
```

Update::: this code solve this problem very elegantly

```
private static int solve(int n, int m) {
int steps = 0;
int cur = n;
ArrayList<Integer> arr = new ArrayList<>();
//Setting a list of the best minimum track.
arr.add(m);
for (int i = 0; !arr.contains(1); ++i)
arr.add((int) Math.round((double) arr.get(i) / 2));
//Aligning the number n to the track and applying it to the best track.(Imagine a stair of steps and you have to reach the top of it, you'll align yourself to one of the steps and then voooom :) )
while (cur != m) {
if (arr.contains(cur))
cur *= 2;
else
cur--;
steps++;
}
return steps;
}
```

This algorithm always traverses **all** possible paths in a tree where one branch represents multiplication and one decrement by 1. The problem is the "**all**", since there would as well be a path like this:

```
n = 2 m = 5
branch selection *2 -1 -1 *2 -1 -1 *2 ...
n after branch 4 3 2 4 3 2 4 ...
```

Which will never abort.

And I doubt that this algorithm will, though it makes perfect sense to you and apart from the obvious issue with the `StackOverflowException`

will solve your problem in all cases. Just a guess, but the problem is to find the minimum-number of multiplications and decrements required to transform `n`

to `m`

. This algorithm will for nearly all cases return 0.

A correct solution would require BFS, unlike the (incorrect) DFS-implementation your solution uses. There is an additional `Set`

for visited nodes required to implement a correct DFS-traversal, invalid solutions would have to be marked explicitly. BFS on the other hand would aswell require to store the depth at which the value was visited:

```
public int solve(int n , int m , int step , Map<Integer , Integer> visitedAt){
//no valid solution
if(n > m * 2 || n <= 0)
return -1;
//a solution was found at step
if(n == m)
return step;
//the node was already visited with less steps
if(visitedAt.containsKey(n) && visitedAt.get(n) <= step)
return -1;
//store the visited value and the step at which it was visited
visitedAt.put(n , step);
//calculate the number of steps required to reach m if the next step is
//either decrement or multiply by two
int dec = solve(n - 1 , m , step + 1 , visitedAt);
int mul = solve(n * 2 , m , step + 1 , visitedAt);
if(dec == -1)//no possibility to reach m by decrementing n
return mul;
else if(mul == -1)//cant reach m by
```

```
```

```
```

```
```

```
```

```
```

```
```#### Post Status

Asked in February 2016

Viewed 3,479 times

Voted 12

Answered 1 times
#### Search

## Leave an answer

```
```

```
```