[C언어, C++] 재귀함수 내에서 재귀호출을 두번 할때 주의점

1. 문제

 

 자료구조 tree공부하다가 입력된 정수를 가지고있는 data를 찾아주는 함수를 작성하고 싶었다. 그 함수는 값을 반환함과 동시에 tree를 전체적으로 탐색하는 역할을 수행해야한다. Tree를 직접 구성해보신 분들은 알겠지만, tree의 탐색은 재귀함수로 작성하는 것이 정말 간편하다. (나도 내입에서 재귀함수가 편하다고 할줄은 몰랐다......)

 

 문제는 여기서 발생한 것이다. root → 왼쪽 트리 → 오른쪽 트리 순으로 탐색하는 전위탐색을 구현하였는데, 왼쪽 탐색을 진행하여 결과가 없을 때, return문이 중간에 끼어있으면 오른쪽 트리를 탐색하지 않고 재귀를 멈추는 오류가 발생하였다. 따라서 재귀호출 안에서 재귀호출을 두번할 때 발생하는 문제에 대해 알 수 있게 코드를 작성해보았다.

 

2. 해결과정

 

 내가 작성하려했던 코드는 다음과 같다.

 

Node* PreorderSearchTree(int data, Node* Node) {
	if (Node->data == data)
    	return Node;
    return PreorderSearchTree(int data, Node* Node->left);
    return PreorderSearchTree(int data, Node* Node->right);
}

 

 실제로 작성한 코드가 아니라 이해를 돕기위한 코드이므로, 핵심적인 문장만 작성하였다. 보면 매개변수로 받은 노드의 data와 입력된 data를 비교하여 일치하면 현재 노드의 주소를 보내고, 아니면 왼쪽과 오른쪽을 차례로 재귀호출하여 탐색하는 코드이다. 문제는 여기에 있었다

 

 중간에 있는 return preorderSearchTree(int data, Node* Node->left); 문장때문에, 탐색이 완료가 되던 말던, 오른쪽 트리의 탐색을 위한 재귀호출이 되지 않는다는 것이다. 내가 이런 코드를 작성한 이유는 재귀호출을 하여도, return문이 없다면, 값이 반환되지 않는다고 생각했기 때문이다. 다시말하면 다음과 같은 코드는 값을 반환하지 않는다고 생각하였다.

 

 

Node* PreorderSearchTree(int data, Node* Node) {
	if (Node->data == data)
    	return Node;
    PreorderSearchTree(int data, Node* Node->left);
    PreorderSearchTree(int data, Node* Node->right);
}​

 

 결국 return문이 없으니 재귀를 하여도 반환하지 않는다고 생각했다. 따라서 다음과 같은 코드를 작성해보았다.

 

#include <stdio.h>

int test(int num);

int main(void) {
	int result = 20;
	result = test(2);
	printf("%d", result);
}

int test(int num) {
	if (num == 1)
		return 1;
	test(num - 1);

}

 

 코드를 설명하자면, result 변수에 20을 설정하고, test()라는 재귀함수를 호출하였다. 내부적으로 이 함수는 한 번 재귀호출을 실행하게 구성하였다. 그러자 결과는 '1'이 나왔다. 결론을 말하자면 return문 없이도 값이 반환되었다는 것이다. 이 부분을 그림으로 설명하면 다음과 같다.

---

---

 그림을 보면 알겠지만, main()에서 호출된 test()함수는 한번 더 내부적으로 test() 함수를 호출하는데 이때, return문 뒤에서 호출되는 것이 아니라 독립적으로 test()함수 만이 호출된다. 그러나 return문 없이 호출된 test() 함수가 반환한 값인 '1'이 결과적으로는 main() 함수에 존재하는 result 변수에 저장되는 것을 볼 수 있다.

 

3. 결론

 

 결론은 순환 함수에서 재귀호출을 두번 할 때는, return문을 사용하지 않는 것이 좋다. return문은 종료조건에만 사용하는 것이 코드가 꼬이는 것을 막을 수 있다. 그리고 return문 없이 재귀호출을 하여도 결과적으로 값이 반환된다는 것을 알 수 있다.