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

Answers


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 2016
Viewed 3,479 times
Voted 12
Answered 1 times

Search




Leave an answer