这个递归函数可以在没有 `trav` 指针的情况下工作吗

Question

我正在使用 tries 开发 pset4 拼写器。此函数给出作为 trie 加载的字典的大小。这个函数可以在不使用我正在使用的 trav 指针的情况下工作吗？我是否必须指向以前的位置，或者这是不必要的吗？

是否会在函数调用中记住我的位置，并且每次我递归调用函数时，指向 sizer 的指针将仅是特定于该调用的东西？一旦我将控件返回到之前的函数，它会在我调用递归函数之前在之前的位置运行，还是我必须将它专门指向之前的位置？

unsigned int size(void)
{    
    node *trav = root;
    int ctr = 0;
    for (int i = 0; i < N; i++)
    {       
            //Sizer is also a node pointer initialized to root globally
            if (sizer -> children[i] == NULL)
            {
                continue;

            }
            else
            {   
                //Store the current value of sizer 
                trav = sizer;

                //Change sizer to point to its child
                sizer = sizer -> children[i];

                if ((sizer -> is_word) == true)
                {
                    ctr ++;
                }
                // recursively call size again
                int x = size();
                ctr += x;

                /*After adding the number all the words IN THE CHILDREN
                  of this particular child, I want to point to the 
                  original `sizer`, so that i can move on to the next 
                  child and repeat the same for its chidren. To do that 
                  i need something to point back to original position
                */
                sizer = trav;

            }

    }

    return ctr;

Answer 1

Can this function work without using the trav pointer which i am using .

嗯……不，不是这个功能。这里的问题是 sizer 是全局的，所以当您希望代码更改它并稍后恢复它时，您将需要一个额外的变量来存储更改前的值。

但是，为什么要使用全局变量呢？

如果将指针传递给“当前根”，则可以避免 trav 并且获得没有全局变量的更简洁的设计。

类似于:

unsigned int size(node *sizer)
{    
    unsigned int ctr = 0;       // notice: changed to unsigned to match the return type
    for (int i = 0; i < N; i++)
    {       
        if (sizer -> children[i] != NULL)
        {
            if ((sizer->children[i]->is_word) == true)
            {
                ctr ++;
            }
            // recursively call size again while passing sizer->children[i]
            ctr += size(sizer->children[i]);
        }
    }

    return ctr;
}

现在每个递归调用都有自己的 sizer 变量，因此您永远不需要更改 sizer，因此您不需要存储到 trav变量。