这些递归遍历函数在没有返回语句的情况下如何工作？ [关闭]

Question

我这里有一个二叉搜索树的代码，它带有通过前序、后序和中序遍历来遍历树的辅助函数。我很困惑，因为这些函数递归地调用自己，但没有 return 语句。我认为所有递归函数都需要一个基本情况才能正常工作，否则它们将无限地调用自己。有人能解释一下为什么会这样吗？

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int data;
    Node *left;
    Node *right;

};

class BSTree {
    private:
        Node *root;
        void insert_h(int, Node *);
        void preorder_h(Node *);
        void inorder_h(Node *);
        void postorder_h(Node *);
    public:
        void insert(int);
        void generateBST(vector<int>);
        void preorderTraverse();
        void inorderTraverse();
        void postorderTraverse();

    BSTree() {
        root = NULL;
    }

};

void BSTree::insert_h(int value, Node *curr) {
    if(value <= curr->data) {
        if(curr->left != NULL)
            insert_h(value, curr->left);
        else {
            curr->left = new Node;
            curr->left->data = value;
            curr->left->left = NULL;
            curr->left->right = NULL;
        }
    }
    else if(value > curr->data) {
        if(curr->right != NULL)
            insert_h(value, curr->right);
        else {
            curr->right = new Node;
            curr->right->data = value;
            curr->right->left = NULL;
            curr->right->right = NULL;
        }
    }

}

void BSTree::insert(int value){
    if(root != NULL)
        insert_h(value, root);
    else {
        root = new Node;
        root->data = value;
        root->left = NULL;
        root->right = NULL;
    }

}

void BSTree::generateBST(vector<int> v){
    for (auto x = v.begin(); x != v.end(); ++ x)
        insert(*x); 

}

void BSTree::preorder_h(Node *curr) {
    if (curr != NULL) {
        cout << curr->data << endl;
        preorder_h(curr->left);
        preorder_h(curr->right);
    }

}

void BSTree::preorderTraverse(){
    preorder_h(root);

}

void BSTree::inorder_h(Node *curr) {
    if (curr != NULL) {
        inorder_h(curr->left);
        cout << curr->data << endl;
        inorder_h(curr->right);
    }

}

void BSTree::inorderTraverse(){
    inorder_h(root);

}

void BSTree::postorder_h(Node *curr) {
    if (curr != NULL) {
        postorder_h(curr->left);
        postorder_h(curr->right);
        cout << curr->data << endl;
    }
    
}

void BSTree::postorderTraverse(){
    postorder_h(root);

}

int main() {
    vector<int> v = {3,6,2,8,1,2,9,7};
    BSTree T;
    T.generateBST(v);
    cout << "---------" << endl;
    T.preorderTraverse();
    cout << "---------" << endl;
    T.inorderTraverse();
    cout << "---------" << endl;
    T.postorderTraverse();
    return 0;

}

这些是我特别困惑的功能：

void BSTree::preorder_h(Node *curr) {
    if (curr != NULL) {
        cout << curr->data << endl;
        preorder_h(curr->left);
        preorder_h(curr->right);
    }

}

void BSTree::preorderTraverse(){
    preorder_h(root);

}

void BSTree::inorder_h(Node *curr) {
    if (curr != NULL) {
        inorder_h(curr->left);
        cout << curr->data << endl;
        inorder_h(curr->right);
    }

}

void BSTree::inorderTraverse(){
    inorder_h(root);

}

void BSTree::postorder_h(Node *curr) {
    if (curr != NULL) {
        postorder_h(curr->left);
        postorder_h(curr->right);
        cout << curr->data << endl;
    }
    
}

void BSTree::postorderTraverse(){
    postorder_h(root);

}

Answer 1

在以

_h

结尾的辅助函数中，您可以将叶节点的基本情况解释为：

if (curr == NULL)
    return;

Answer 2

在辅助函数中（以_h结尾），基本情况是

curr == NULL

。所以上面写的代码基本等价于：

void BSTree::inorder_h(Node *curr){
    if (curr != NULL) {
        inorder_h(curr->left);
        cout << curr->data << endl;
        inorder_h(curr->right);
    }
    return;
}

或

void BSTree::inorder_h(Node *curr){
    if (curr != NULL) {
        inorder_h(curr->left);
        cout << curr->data << endl;
        inorder_h(curr->right);
    }
    else{
        return;
    }
}

所以这基本上是一样的：

void BSTree::inorder_h(Node *curr) {
    if (curr == NULL) {
        return;
    }
    inorder_h(curr->left);
    cout << curr->data << endl;
    inorder_h(curr->right);
}

在第三种情况下，明确需要返回，因为您希望在达到基本情况时尽早返回。但是在前两种情况下，不需要返回，因为当非基本情况失败（达到基本情况）时，函数无论如何都会终止。

Answer 3

我认为所有递归函数都需要一个基本情况才能正常工作，否则它们将无限地调用自己。

这是真的，但这与您之前对

return

陈述的观察无关。注意“基本情况”中的“情况”一词——这是否让您想起任何 C++ 语句？也许

switch

-

case

，哪个是分支控制结构之一？分支是基本案例所需要的，不一定是

return

.

虽然

switch

可用于递归，但

if

语句更为典型。要发现基本情况，请查找允许程序流跳过所有递归调用的

if

语句。是的，有些人喜欢使基本案例易于发现，这通常涉及

return

声明，如

void BSTree::preorder_h(Node *curr) {
    if (curr == NULL) {
        // Base case
        return;
    } else {
        cout << curr->data << endl;
        preorder_h(curr->left);
        preorder_h(curr->right);
    }
}

然而，这只是风格。上面的代码等同于下面的代码，其中基本情况是不进入

if

.

的分支

void BSTree::preorder_h(Node *curr) {
    if (curr != NULL) {
        cout << curr->data << endl;
        preorder_h(curr->left);
        preorder_h(curr->right);
    }
    // else the base case, which is to do nothing, so no code is needed
}

相同的逻辑，只是代码更少。

成功的递归需要在某个点进行分支，将代码路径划分为至少两种情况，其中一种是基本情况。是否需要

return

语句遵循与非递归函数相同的规则——返回

void

的函数不需要有显式的

return

语句。