(С++) Рекурсия

[Troi666]

Всем доброго времени суток! Раньше никогда не использовал рекурсию, однако считал ее аналогом цикла, более ресурсоемкого, но изящного. Однако теперь захотелось попробовать поработать с бинарными деревьями (сразу говорю - лаба не обязательная )

Итак..в методичке приведена функция для обхода ВСЕГО дерева:

Подскажите, плиз, как она работает...и как мы можем вообще попасть в строчку walkTree(p->pright);. Заранее спасибо!

template<class T>
void walkTree(TNode<T>* p)
{
 if(p)
 {
  walkTree(p-.pleft);
  cout<<p->value<<' ';
  walkTree(p->pright);
 }
}

[Sazary]

template<class T>
void walkTree(TNode<T>* p) //принимаем указатель на элемент дерева
{
 if(p)  // если этот элемент существует...
 {
  walkTree(p->pleft);  // то спускаемся на уровень ниже и смотрим левую ветку
  cout<<p->value<<' ';  // тут выводим значение поля текущего элемента
  walkTree(p->pright);  // а тут спускаемся и смотрим правую ветку
 }
}

.и как мы можем вообще попасть в строчку walkTree(p->pright);.

Ну ведь pright - это указатель на тип.

[Troi666]

Ну ведь pright - это указатель на тип.

Согласен! Но не произойдёт ли так, что: мы вызываем функцию обхода walkTree. Она начинает свою работу. Доходит до строчки walkTree(p->pleft); , где вызывает снова саму себя. И так до конца ветки. Получается, что сюда: cout<<p->value<<' '; walkTree(p->pright); мы не попадаем никогда?

[Sazary]

Доходит до строчки walkTree(p->pleft); , где вызывает снова саму себя. И так до конца ветки

Да. Дойдем до конца ветки, после чего наткнемся на NULL. Условие ( if(p) ) не выполнится и мы выйдем из функции. Таким образом управление вернется к функции (walkTree), которая обрабатывает предыдущий элемент и мы перейдем к следующей инструкции. То есть, к

cout<<p->value<<' ';

[Troi666]

Хмм...начинаю понимать Тоесть сколько раз функция вызывает саму себя - столько раз она запоминает своё состояние? Если да - то как? Копирует свой код + параметры в оперативную память, или иначе? И если всё так - то, как же нам насовсем выйти из функции (не именно из этой, а из любой рекурсивной)? Что даст return? Переход на 1 функцию вверх или выход из всей рекурсивной функции целиком?

[Sazary]

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

Тоесть сколько раз функция вызывает саму себя - столько раз она запоминает своё состояние? Если да - то как?

Адрес возврата и локальные переменные функции помещаются в стек.
Таким образом ничто не потеряется.

И если всё так - то, как же нам насовсем выйти из функции (не именно из этой, а из любой рекурсивной)? Что даст return? Переход на 1 функцию вверх или выход из всей рекурсивной функции целиком?

Выход из функции, вызванной рекурсивно, возвращает управление в функцию, которая ее вызвала. К следующей за вызовом инструкции.

[Troi666]

Sazary Спасибо! Теперь почти всё стало ясно Остаётся 1 вопрос. Можем ли мы вернуться на несколько уровней функции выше "вручную" ? Допустим функция погрузилась на 7 уровней рекурсии. а нам стал очень нужен 2-й. Можем ли мы как-то на него перейти?

[Sazary]

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

Допустим функция погрузилась на 7 уровней рекурсии. а нам стал очень нужен 2-й. Можем ли мы как-то на него перейти?

Вроде, как-то можно.. Но я этим вопросом не интересовался )

Интересно, а зачем вам может понадобиться вернуться на несколько уровней?
Собственно, ведь рекурсия обычно и используется там, где нужно последовательно обойти все вершины (или еще что-то).

[Troi666]

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

Задание: Построить бинарное дерево выражений для заданного выражения: ((3+4)*(8-(3*2)))*(9*(7+4))

[Sazary]

Troi666, ну попробуйте
С деревьями знаком довольно поверхностно, поэтому поиск вам больше подскажет )