Ошибка StackOverflow при использовании recursion

Question

Я пытаюсь получить число (n) до (m), и для меня алгоритм имеет смысл, но он всегда сбой с ошибкой Stackoverflow. любая помощь? вот мой код:

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 ::: этот код решить эту проблему очень элегантно

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

Answer 1

Этот алгоритм всегда проходит все возможные пути в дереве, где одна ветвь представляет собой умножение и одно декремент на 1. Проблема заключается в том, что «все», поскольку также будет такой путь:

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

Который никогда не прерывается.

И я сомневаюсь, что этот алгоритм будет, хотя он имеет для вас смысл, и, кроме очевидной проблемы с StackOverflowException, вы решите свою проблему во всех случаях. Просто догадаться, но проблема заключается в том, чтобы найти минимальное количество умножений и декрементов, необходимых для преобразования n в m. Этот алгоритм будет почти для всех случаев возвращать 0.

Для правильного решения потребуется BFS, в отличие от (неправильной) DFS-реализации, используемой вашим решением. Существует дополнительный Set для посещенных узлов, необходимых для реализации правильного обхода DFS, недействительные решения должны быть отмечены явно. BFS с другой стороны, как хорошо потребуется, чтобы сохранить глубину, на которой побывали значение:

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 multiplying n by 2 
     return dec; 
    else //both lead to valid solutions, find minimum number of steps 
     return Math.min(dec , mul); 
} 

Хотя это решение не совсем элегантный реализация BFS-алгоритм. Но он выполняет требование быть рекурсивным.