如何处理成员函数中的递归？

Question

例如，我有一个empty函数来清除链表：

void empty(Node* head) {
        if (head->next) { empty(head->next); }
        delete head;
        head = nullptr;
    }

但是后来我为链表创建了一个class，所以现在我不需要传递head参数：

void empty() {
        if (head->next) { empty(head->next); }
        delete head;
        head = nullptr;
    }

但是 empty(head->next) 行显然是错误的，因为 empty 没有接受任何参数。我想到了在函数内部创建一个函数（使用 lambda）的想法，就像这样：

void empty() {
        std::function<void(Node*)> emptyWrapper = [&] (Node* l_head) {
            if (l_head->next) { emptyWrapper(l_head->next); }
            delete l_head;
            l_head = nullptr;
        };
        emptyWrapper(head);
    }

但我想知道是否有更好的方法来做到这一点。 Lambdas 最近对我来说有点固定。

Answer 1

直接的解决方案是使用一个辅助函数来完成您的递归函数所做的工作。

class List{
public:
   void empty(){
        if (head) { empty_helper(head); }
        delete head;
        head = nullptr;
    }
private:
// should probably be static to avoid propagating this.

void empty_helper(Node* head) {
        if (head->next) { empty_helper(head->next); }
        delete head;
        head = nullptr;
    }
};

当然还有其他选项可用，例如使其成为非递归的。

我认为在这种情况下不需要 lambda。

Answer 2

注意：正如其他人提到的，您不需要在这里使用递归。此示例假设您出于某些未提及的原因想要或需要。这就是你会使用递归的方式。然而，用循环重构可能是你在漫长的运行.

中应该做的。

您可以制作一个 public 和私有版本的列表：

class list {
public:
void empty();

//...
private:
void empty(Node* head);
// alternatively, you could make this static instead:
static void empty(Node* head);

//...

}

然后你可以调用 empty() 从另一个 empty():

中获取一个参数

void list::empty() {
    if(this->head) {  // check here so ->next won't fail in the helper function.
                      // maybe you should add a check there instead
        empty(this->head);
    }
}

P.S。您可能不应该像我在这里所做的那样到处使用名称 head。这只是我放在一起的一个简单例子。但至少你可以通过这种方式了解总体思路。

Answer 3

一般方法是声明一个 public 成员函数，该成员函数又调用私有静态递归成员函数。

注意名字 empty 听起来很混乱。最好将函数命名为例如 clear.

给你

#include <functional>

//...

class List
{
public:
    //...
    void clear() 
    {
        clear( head );
    }

private:
    static void clear( Node * &head )
    {
        if ( head )
        {
            delete std::exchange( head, head->next );
            clear( head ); 
        }
    }
    //...
}

可以在不定义辅助静态函数的情况下使用相同的方法。

void clear()
{
    if ( head )
    {
        delete std::exchange( head, head->next );
        clear();
    }
}

这是一个演示程序。

#include <iostream>
#include <iomanip>
#include <functional>

template <typename T>
class List
{
private:
    struct Node
    {
        T data;
        Node *next;
    } *head = nullptr;

public:
    void push_front( const T &data )
    {
        head = new Node { data, head };
    }

    friend std::ostream & operator <<( std::ostream &os, const List &list )
    {
        for ( Node *current = list.head; current; current = current->next )
        {
            os << current->data << " -> ";
        }

        return os << "null";
    }

    bool empty() const { return head== nullptr; }

    void clear()
    {
        if ( head )
        {
            delete std::exchange( head, head->next );
            clear();
        }
    }
};

int main() 
{
    List<int> list;

    const int N = 10;

    for ( int i = N; i != 0; )
    {
        list.push_front( i-- );
    }

    std::cout << list << '\n';

    list.clear();

    std::cout << "list is empty " << std::boolalpha << list.empty() << '\n';

    return 0;
}

程序输出为

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> null
list is empty true

如何处理成员函数中的递归？

How to handle recursion in member functions?

c++

recursion

class

singly-linked-list

function-definition