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

Question

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

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

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 是全局的，所以当您希望代码更改它并稍后恢复它时，您将需要一个额外的变量来存储更改前的值。

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

如果将指针传递给 "current root"，则可以避免 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 变量中。

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

Can this recursive function work without the `trav` pointer

c

recursion

trie

cs50