рекурсивные функции

[Kukurudza]

такой вопрос.
проверяю рекурсивно все узлы бинарного дерева на наличие некоторого элемента, чтобы потом его изменить по ссылке. если этот элемент обнаружен как выйти из рекурсии сразу же после это, не просматривая все остальные узлы?

ну вот так например:

T& function (T& element, node* root)
{
    if (root -> element == element) return root->element;
    function(element, root -> left);
    function(element, root -> right);
};

[Сtrl]

Поскольку у вас только один процесс, то по сути именно это и произойдет.

[Kukurudza]

действительно так и происходит. вернее те узлы которые еще не вызывались, уже и не вызовутся, а те уровни функций которые были вызваны но еще не завершили свое выполнение выполнятся до конца, но уже не будут вызывать внутри себя себя же. верно? вроде правильно изъяснился.

[Гром]

Хм, а компилятор не ругается, что значение возвращается не при всех ситуациях? Вообще-то должен.
А как выйти - при обнаружении генерируйте исключение, которое обрабатывайте ниже. См., например, у Страуструпа главу 14.5 "Исключения, не являющиеся ошибками".
Это будет эффективно, однако этот момент необходимо развернуто прокомментировать, т.к. в данном случае исключения выполняют не ту роль, для которой предназначены - сообщение об ошибке.

[An1ka]

Сообщение от Kukurudza

такой вопрос.
проверяю рекурсивно все узлы бинарного дерева на наличие некоторого элемента, чтобы потом его изменить по ссылке. если этот элемент обнаружен как выйти из рекурсии сразу же после это, не просматривая все остальные узлы?

ну вот так например:

T& function (T& element, node* root)
{
    if (root -> element == element) return root->element;
    function(element, root -> left);
    function(element, root -> right);
};

Он не будет работать корректно. Только, если найдет в самом первом элементе. Для последующих вызовов функций нету возврата.

T& function (T& element, node* root)
{
    if (!root) return 0; // Чтобы по нулевому указателю не было обращения
    T *el = 0;
    if (root -> element == element) el = &root->element;
    if ( !el)
	el = &function(element, root -> left);
    if ( !el)
        el = &function(element, root -> right);
    return *el;
};

Как только элемент найдется, то произойдет присвоение адреса указателю, а следующих вызовов не будет и произойдет возврат. То тут еще надо предусмотреть, если элемент не будет найден вообще, а ветвь дерева закончилась. Например, если указатели left или right не указывают на следующий элемент, то их значение должно быть 0, это нужно, чтобы сделать проверку на 0 и не пойти по неправильным указателям.

[Granus]

An1ka,

if (!root) return 0;

Так делать нехорошо, так как возвращается ссылка, т.е. должен быть конкретный объект, а не константа.

Сообщение от Гром

Хм, а компилятор не ругается, что значение возвращается не при всех ситуациях? Вообще-то должен.

Ну, gcc, например, просто ворнинг пишет, а его можно и случайно пропустить)

Сообщение от Kukurudza

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

Первое, что пришло в голову:

T& Object; // найденный элемент

bool function (T& element, node* root) // Функция возвращает true, если в потомках что-то нашлось, иначе false
{
    if (root -> element == element){
        Object=root->element;
        return true;
    };
    // return function(element, root -> left) || function(element, root -> right); Насколько я знаю, большинство компиляторов оптимизируют логическое ИЛИ, и если первый аргумент - true, то второй не вычисляется. На всякий случай далее код, который сработает таким же образом
    if(function(element,root->left)) return true; else return function(element,root->right);
};