C++ 재귀 함수 반환 값

Question

숙제로서, 나는 이진 검색 트리를 구현 중이며 일부 데이터의 위치를 ​​검색하는 부분을 수행 중이며 (나중에 수정/제거 할 수 있음), 여기에 코드 :

node*& bst::search(data& x, node*& pos) { 
    if (pos->get().num == x.num) { 
     return pos; 
    } 
    if (pos->right != NULL) search(x, pos->right); 
    if (pos->left != NULL) search(x, pos->left); 
} 

search(data_to_find, root)을 호출합니다. 내 예제에서 나는이 양식의 정수의 나무했다 : 나는 소자 (3)을 검색하고 싶었 1. 루트 가리키는

1 
2 
    3 

을, 나는 3 포인터를 얻을 것으로 예상하지만, 매번되었다 이 함수는 루트 자체를 반환합니다. 그러면 foo가 값을 반환하지 않는 첫 번째 인스턴스와 관련이있을 수 있다고 생각 했으므로 search(x, pos->right)을 return search(x, pos->right)으로 변경하고 왼쪽은 같았습니다. 이번에는 모든 것이 정상적으로 수행되었습니다. 이것은 내가 그냥 진술이 거짓 인 경우, 그것은 스틸 사진의 경우에 반환 할 것을 지정하지 않은 있지만 그것은

int foo(int x = 0) { 
    if (x == 1) { 
     return x; 
    } 
    x++; 
    foo(x); 
} 

을 반환 이해하기 위해 다음과 같은 더미 기능을 몇 가지 실행을하려고 나를 혼동했다 분명히 오류 "값을 반환해야 foo는"는 결과

int boo() { 
    return 1; 
} 

int foo() { 
    boo(); 
} 

및 foo()라고 : 작품과 출력 1. 나는 foo(0) 그냥 어떤 foo(1) 내가이 시도 있는지 확인하기 위해 재귀 반환 반환 어쩌면 생각 boo()에서 return boo()으로 수정했습니다. 내 질문에 왜 첫 번째 사례가 뿌리를 출력합니까? 왜 두 번째 사례가 효과가 있습니까?

Answer 1

여기서의 문제는 재귀 호출의 반환 값을 원래 호출자에게 전파하지 않는다는 것입니다. 그대로, 그 호출이 돌아 오면 값은 버려집니다.

당신이 당신의 매치를 찾지 못하는 경우에 서면으로 기능하는 것은 아무것도 반환하지 못합니다. 이것은 정의되지 않은 동작입니다. 루트 노드를 얻는다는 사실은 정의 된 결과가 아니라 컴파일러 나 현재의 메모리 레이아웃의 특징입니다.

@Mike가 지적했듯이 이진 트리의 경우 검색 값이 현재 노드가 보유한 값보다 크거나 작은 지 여부에 따라 검색에서 하나의 하위 트리를 탐색해야합니다 . 전통적으로 왼쪽 트리는 현재 노드보다 작은 값을 보유하고 오른쪽 트리는 더 큰 값을 보유합니다.