разница в обратном рекурсивном вызове и просто рекурсивном вызове

Question

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

ниже - функция, которую я написал, и вывод в настоящее время корректен, используя эту реализацию.

 if(root == nullptr)
    return;

inorderDump(root->leftSubtree());
cout << root->value() << endl;
inorderDump(root->rightSubtree());

Мой вопрос: почему эти рекурсивные вызовы не нуждаются в операторе return? Следующая функция, написанная точно так же с оператором return, не работает.

ниже - пример той же функции при использовании оператора return и неправильного вывода.

 if(root == nullptr)
    return;

return inorderDump(root->leftSubtree());
cout << root->value() << endl;
return inorderDump(root->rightSubtree());

Итак, я думаю, вкратце, что я пытаюсь сказать, в чем разница между рекурсивным вызовом функции с оператором return и без него, и когда вы выбираете одну из них над другой? Спасибо!

Ниже приведены примеры данных, которые я использую для проверки этих рекурсивных функций.

16000 24507 64025 99756 114258 163016 196448 198668

Answer 1

Рекурсия состоит из вызова вызывающей функции из вызываемой функции.

Чтобы завершить рекурсивную цепочку вызовов, должно быть условие выхода.

Поставленный вопрос предполагает, что рекурсивный вызов зависит от возврата чего-либо. Это не тот случай. Это понятная путаница, вызванная факториальными упражнениями и упражнениями Фибоначчи.

В приведенном выше примере 1 рекурсивный вывод проявляется выводом в std :: cout.

В примере 2 двойной вызов return контрпродуктивен - поскольку второе возвращение никогда не может быть выполнено - поскольку поток функции завершается первым вызовом. Тот факт, что пример 2 вызывает сам себя, не означает, что будет выполнен второй возврат.

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

Опять же, рекурсия не требует, чтобы функция возвращала значение.

Answer 2

Я не знаю, где именно твоя путаница, поэтому я добавлю сюда более широкую сеть.

Рекурсия не имеет отношения к возвращению и все, что связано с вызовом.

Вот что такое рекурсия:

... foo(...)
{
    ...
    ... foo(...)...
    ...
}

foo - это функция, принимающая любое количество и тип аргументов и возвращающая что-либо (включая void или ничего не возвращающая). Если где-то внутри foo вы вызываете foo, то foo рекурсивно. Вот и все. Это рекурсия. Функция, вызывающая сама себя.

Ваша функция (первая) имеет инструкцию cout, она будет печатать текущий узел. return не имеет смысла.

Проблема со второй версией проста: после рекурсивного вызова в левую часть дерева функция немедленно возвращается, никогда не достигая оператора cout, таким образом, никогда не печатая и никогда не выполняя правую часть рекурсии дерева.

Answer 3

Во втором случае программа просто пройдет по всем левым поддеревьям, пока не найдет нулевое значение, и больше ничего не будет делать, потому что оператор return заставляет вас выйти из функции, поэтому она не будет перемещаться по правым поддеревьям или печатать что-нибудь.