Member 13234467 Ответов: 5

Как использовать функцию return в рекурсии.

У меня есть следующий код для обхода дерева по порядку:
void inOrder(struct node* r)
{
if (r==NULL)
return;

else{
inOrder(r->left);
printf("%d ", r->value);
inOrder(r->right);
    }
}


У меня есть это глупое сомнение:

Когда самый нижний левый дочерний элемент передается как root, он не является нулевым.
На следующей итерации корень будет равен нулю (так как левый дочерний элемент самого нижнего левого дочернего элемента будет равен нулю), и он столкнется с возвращением.

Разве этот оператор return не передаст элемент управления основной функции (или где бы она ни вызывалась) без какой-либо печати?


Вернется по-разному ведут себя в рекурсию?

Что я уже пробовал:

<pre>
void inOrder(struct node* r)
{
if (r==NULL)
return;

else{
inOrder(r->left);
printf("%d ", r->value);
inOrder(r->right);
    }
}

5 Ответов

Рейтинг:
2

KarstenK

Если вы вернетесь, то вернетесь к вызывающей функции, а не непосредственно в main.

Отладьте стек вызовов,чтобы понять его. Какой-то выход всегда помогает.

void inOrder(struct node* r)
{
printf("inoder %d ",(int) r);//debug output
if (r==NULL)
return;
 else{
//do your recursion work
printf("l-call: %d ", l->value);
inOrder(r->left);
printf("r-call: %d ", r->value);
inOrder(r->right);
    }
}

Рейтинг:
0

OriginalGriff

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

Предположим, у вас есть дерево:

    A
   / \
  B   C
 / \
D  E
Вы передаете в функцию.
Это ноль? Нет-вызовите его рекурсивно с правым узлом: C. Это складывает контекст.
На этот раз вы проверяете, является ли C нулевым. Это не так, поэтому вы рекурсивно вызываете функцию, передавая ей пустой узел C. Right. Этот контекст получает стеки (так что теперь там есть два контекста)
Сравните с нулем. Это так, поэтому вы немедленно возвращаетесь из функции. Удалите верхний контекст и восстановите его.
Выполнение продолжается с оператора сразу после последнего вызова, где вы обрабатывали узел C. Вы печатаете значение " C " и повторяете процесс для левых узлов.

Попробуйте сделать это с помощью отладчика, и вы скоро поймете эту идею!

Рейтинг:
0

Peter_in_2780

Нет. Он вернется, конечно, но только на один уровень, а не полностью к исходному вызывающему. Постройте простое дерево, скажем, из 5 или 6 узлов, а затем шагайте через свой код с помощью отладчика. Следите за вложенными вызовами и возвратами.

Рейтинг:
0

RAMASWAMY EKAMBARAM 

void main()
{
	struct node *pn;
	int a = 5, b = 8, c;
	
	...
	<some code>
	...
	inorder(pn);
	c = a + b;     // address of this instruction is 12345680
	<some more code>
}

int fun()
{
	struct node n;
	
	...
	<some code>
	....
	
	inorder(&n);
	getchar();   // address of this instruction is 12345760
	<some more code>
}

void inorder(struct node *r)
{
	if (r==NULL)
		return;
	else
	{
		inOrder(r->left);
		printf("%d ", r->value);  // address of this instruction is 12345900
		inOrder(r->right);
	}
}

/*
	JUST before calling inorder()
	in the call from main() the value 12345680 is pushed onto the stack
	in the call from fun()  the value 12345760 is pushed onto the stack
	in the (recursive) call from inorder()  the value 12345900 is pushed onto the stack
	
	i.e. in each case the address of the next instruction (immediately following the function call) is pushed onto the stack
	so that processing continues from this point (next instruction) in the CALLER after the called function completes normally 
		(end of function OR  'return' instruction in the middle of the function)
	It makes no difference whether the call is recursive or not.
	if you have some idea of 32 bit x86 registers 
		'eip' always holds the address of the instruction to be executed next
		'esp' points to the last value pushed on the stack - 
			this is the return address (12345680 / 12345760 / 12345900) in our example
		the 'return' instruction will result in something like this (in C syntax):
			eip = *esp++; // esp++ since stack grows downward (generally including x86)
			
			Since 'esp' points to these values, the return address is automatically assigned to 'eip'
		So processing continues from whatever instruction 'eip' points to i.e. next instruction in CALLER.

*/

Рейтинг:
0

Patrice T

Цитата:
У меня есть это глупое сомнение

Существует инструмент, который позволяет вам видеть, что делает ваш код, его имя-отладчик. Освоение отладчика не является обязательным, оно обязательно для любого программиста, без исключения.
Это также отличный инструмент обучения, потому что он показывает вам реальность, и вы можете увидеть, какие ожидания соответствуют реальности.
Когда вы не понимаете, что делает ваш код или почему он делает то, что делает, ответ таков: отладчик.
Используйте отладчик, чтобы увидеть, что делает ваш код. Просто установите точку останова и посмотрите, как работает ваш код, отладчик позволяет вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения, это невероятный инструмент обучения.

Отладчик-Википедия, свободная энциклопедия[^]
Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]
Базовая отладка с помощью Visual Studio 2010-YouTube[^]
Отладчик здесь для того, чтобы показать вам, что делает ваш код, и ваша задача-сравнить его с тем, что он должен делать.
В отладчике нет никакой магии, он не находит ошибок, он просто помогает вам. Когда код не делает того, что ожидается, вы близки к ошибке.