Как данные возвращаются на главную?

Question

Я написал этот кусок кода, и он, кажется, работает, но когда я повторно анализирую его, мне интересно, как данные (минимум) возвращаются в основную функцию?
Учитывая это двоичное дерево:

           17
       14      19
    12       18  20
       13          21

И этот код:

struct Node {
   int data;
   Node* left;
   Node* right;
};

int min(Node* root) {
   if(root == NULL)
      return 0;
   else if(root->left == NULL)
      return root->data;
   else
      min(root->left);
}

Последний вызов min(Node*) вернет root->data, но у вызывающего абонента нет return в min(root->left). Все return уже пропущены в предыдущем min(Node*).

Answer 1

Этот код содержит неопределенное поведение, так что с точки зрения юриста-языка это просто удача, что он работает.

На практике, наиболее вероятно, что происходит (на архитектурах X86), это то, что функция min()сохраняет результат в регистре eax.

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

Короче говоря, min(root->left); компилируется точно так, как если бы это было return min(root->left); из чистой удачи.

Редактировать :

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

Answer 2

Вы действительно имели в виду "и это [случайно] работает [на тестовых данных, которые я пробовал]?"Для того, чтобы это работало, последняя ветвь должна иметь вид else return min(root->left); Ваш компилятор выдал какие-либо предупреждения о возможных путях управления без return?

Answer 3

Код имеет неопределенное поведение, поэтому он работает случайно. В C ++ недопустимо, чтобы поток управления достигал конца функции, отличной от void, без возврата значения (единственное исключение - main).

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

---

Что может происходить, так это то, что возвращаемое значение сохраняется в регистре (обычно eax, я полагаю) самым вложенным вызовом, а другие вызовы фактически не выполняют *. 1011 *, они не перезаписывают это. Однако обратите внимание, что это чисто предположение и может измениться с помощью другого компилятора, разных флагов компиляции и т. Д. Неопределенное поведение не определено и на него нельзя полагаться.