递归函数缺少 Return 语句

Question

我是递归的新手，我不明白为什么这个函数不能编译。它显然缺少 return 语句。从测试来看，我的 return 语句似乎也没有 return?

// recursive search method
public BinaryTree<T> recursiveSearch(BinaryTree<T> t, T key) {
    if (key.compareTo(t.getData()) < 0) {
        if (t.getLeft() != null) {
            recursiveSearch(t.getLeft(), key);
        } else {
            return null;
        }
    } else if (key.compareTo(t.getData()) > 0) {
        if (t.getRight() != null) {
            recursiveSearch(t.getRight(), key);
        } else {
            return null;
        }
    } else if (key.compareTo(t.getData()) == 0) { // key is found
        return t;
    } else { // not in binary tree
        return null;
    }
}

Answer 1

问题出在进行递归调用的 if 分支内部的行上。

您的代码在到达任何 else 分支时都会正确运行，因为它们都有 return null。但是，如果代码采用 if 分支之一，则控件将到达您的方法的末尾而不会遇到 return。修复很简单 - 添加缺失的 returns:

return recursiveSearch(t.getRight(), key);

Answer 2

是的，它缺少递归语句的 return 语句。

public BinaryTree<T> recursiveSearch(BinaryTree<T> t, T key)
{
    if (key.compareTo(t.getData())<0){
        if (t.getLeft() != null) {
            recursiveSearch(t.getLeft(), key); // This case doesn't return anything
        } else { return null;}
    } else if (key.compareTo(t.getData())>0) {
        if (t.getRight() != null) {
            recursiveSearch(t.getRight(), key); // This case doesn't return anything
        } else {return null;}
    } else if (key.compareTo(t.getData())==0){ // key is found
        return t;
    } else {
        //not in binary tree
        return null;
    }
}

我不知道你的程序逻辑，但如果我不得不猜测，你可能想在递归调用中添加一个 return 语句。像这样，

return recursiveSearch(t.getLeft(), key);

和

return recursiveSearch(t.getRight(), key);

递归函数缺少 Return 语句

Recursive Function Missing Return Statement

java

recursion

binary-search-tree