Что не так с рекурсией в C

#c #recursion

#c #рекурсия

Вопрос:

Я попытался выполнить поиск узла дерева с определенным значением в двоичном дереве поиска.
Итак, я использовал рекурсию, но это не сработало хорошо.
Я хочу знать, что не так с функцией.

Кто-то сказал, что я должен возвращать функцию, когда я вызываю ее саму по себе.
Это действительно сработало, но я не понимаю, почему. Может ли кто-нибудь объяснить мне, как
рекурсия действительно работает и что, если возвращаемый тип — void? Спасибо!

 typedef struct node
{
    struct node* left;
    struct node* right;
    int val;
}treeNode;
int searchTree(treeNode *T, int key, treeNode *T1, treeNode** p)
{
    if(!T)
    {
        *p=T1;
        return 0;
    }
    else if(T->val==key)
    {
        *p=T;
        return 1;
    }
    else if(T->val<key)
    {
        searchTree(T->right,key,T,p);
    }
    else
    {
        searchTree(T->left,key,T,p);
    }
    return 1;
}

1. «это не сработало хорошо», что именно означает?

2. Вы не должны return 1 выполнять дочерние запросы, а скорее то, что должны searchTree возвращать внутренние вызовы.

3. «Это не сработало хорошо» означает, что когда я использую searchTree для вставки массива с циклом for, вставляется только первый элемент массива.

4. Вы не используете возвращаемое значение из searchTree

5. Не могли бы вы объяснить, почему я должен использовать возвращаемое значение из дерева поиска?

Ответ №1:

вы пропустили возврат значения рекурсивного вызова

если вам нужно выполнить рекурсивный вызов, это не зря 😉

 int searchTree(treeNode *T, int key, treeNode *T1, treeNode** p)
{
    if(!T)
    {
        *p=T1;
        return 0;
    }
    else if(T->val==key)
    {
        *p=T;
        return 1;
    }
    else if(T->val<key)
    {
        return searchTree(T->right,key,T,p);
    }
    else
    {
        return searchTree(T->left,key,T,p);
    }
}

Обратите внимание, что, поскольку рекурсия является терминальной, компилятор может удалить ее и создать цикл…и вы тоже можете сделать это самостоятельно;-)

1. Привет, Лю, снова 😉

2. это зависит от случая, здесь это просто int , поэтому значение может быть возвращено в регистре, иначе оно находится в стеке

3. вот так, у нас есть ссылка для чата