Рекурсивный обход двоичного дерева не завершается в операторе возврата

Question

Я создал класс, который заполняет двоичное дерево азбукой Морзе. Где перемещение влево означает DOT, а перемещение вправо означает DASH. Все шло отлично, пока я не напишу метод кодирования для преобразования символа альфа в строку кода Морзе. Метод должен рекурсивно выполнять предварительный обход дерева (создавая строку кода Морзе по пути), пока не найдет целевой символ и затем не вернет эту строку.

Однако по какой-то причине моя рекурсия не заканчивается в моем базовом случае. Он просто продолжает весь ход. Я приложил свой код для метода ниже. Почему оператор return в операторе if не вызывает и не завершает метод?

Извините, если это неоднозначно, но я не хотел публиковать 300 строк кода для всего моего проекта, когда кто-то умнее, чем я, сразу заметил бы проблему.

Спасибо за любую помощь

    //wrapper class
    //@parameter character is the character to be encoded
    //@return return the morse code as a string corresponding to the character

    public String encode(char character){

        return encode(morseTree, character, "");


    }


    //@Parameters tree is the binary tree is the tree to be searched, 
    //element is the target character trying to be foudn, s is the string being used to build the morse code
    //@return returns the morse code that corresponds to the element being checked

    public String encode(BinaryTree<Character> tree, char target, String s){


        if(tree.getData() == target){  //if the data at the current tree is equal to the target element
            //return the string that is holding the morse code pattern for this current traversal
            return s;
        }else{
            if(tree.getLeftSubtree() != null){
                    //Traverse the left side, add a DOT to the end of a string to change the morse code
                    encode(tree.getLeftSubtree(), target, s + DOT);
            }

            if(tree.getRightSubtree() != null){
                    //Traverse the left side, add a DOT to the end of a string to change the morse code
                    encode(tree.getRightSubtree(), target, s + DASH);
            }
        }

        //The code should never get this far!
        return s;
    }

Answer 1

Ваши звонки в блоке else не возвращаются - они, вероятно, должны, например, так:

if (tree.getLeftSubtree() != null) {
   // Traverse the left side, add a DOT to the end of a string to
   // change the morse code
   return encode(tree.getLeftSubtree(), target, s + DOT);
}

if (tree.getRightSubtree() != null) {
    // Traverse the left side, add a DOT to the end of a string to
    // change the morse code
    return encode(tree.getRightSubtree(), target, s + DASH);
}

Но что вы хотите сделать, если левые и правые поддеревья равны нулю?И если они оба ненулевые , что вы хотите вернуть?

Обратите внимание, что только потому, что ваш базовый вызов уже возвращен, он возвращает только для этого единственного вызова - не все остальные вызовы в стеке.Повторение не заменяет кадр стека новым вызовом - оно просто добавляет другой кадр стека ¹ .Возвращение из этого нового стекового фрейма просто возвращает вас туда, где вы были.

---

¹ Да, я знаю о хвостовой рекурсии.Но давайте не будем путать вещи.