# Developers Planet

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.
for (int i = 0; !arr.contains(1); ++i)

//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;
}
``````

Paul February 2016

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 2016Viewed 3,479 timesVoted 12Answered 1 times Search Leave an answer ```
``` ```
``` ```
``` Quote of the day: live life .btn-primary{ background-color: #f44336 !important; border-color: #f44336 !important; } Devs Planet ® 2014-2016 www.devsplanet.com Devs Planet © all rights reserved Quick Actions Search // Used to toggle the menu on small screens when clicking on the menu button function myFunction() { var x = document.getElementById("navDemo"); if (x.className.indexOf("w3-show") == -1) { x.className += " w3-show"; } else { x.className = x.className.replace(" w3-show", ""); } } ```