위의 예제처럼 4개의 데이터를 가진 Linked list data가 있다고 해 보자. (서브스크립트는 그냥 순서를 나타내려고 붙임.)
위의 예제에서 동일한 데이터가 있는지 검색하려면 non-recursive 접근방식으론 이정도로 될 것이다.

DATA dataForFind; // 찾고자 하는 데이터

NODE* current = head;

for(;;){
  if(current->data == dataForFind){
     printf("찾았음");
     return;
  }
  else {
     if (current->next==NULL){
        printf("못찾음ㅋ");
        break;
     }else current = current->next;
}
return;

이정도가 될 거임.

recursive한 구현은?

int main(){
   ....
   if(recursiveFind(head, dataForFind))
      printf("찾았음");
   else printf("못찾음");
   ....
}

bool recursiveFind(NODE* current, DATA dataForFind){
   if(current->data == dataForFind){
        return true;
   else {
        if (current->next==NULL) return false;
        else 
           return recursiveFind(current->next, dataForFind);
   }
}

이렇게 하면 다음 노드에 대해 recursiveFind()함수 내에서 자신을 재귀호출함으로서 자식 노드에 대해 데이터가 맞는지 검사할 수 있고,
데이터가 있을 경우 연쇄적으로 재귀호출을 빠져나오면서 연쇄적으로 true를 리턴함으로서 최종 결과값은 true로 나오게 됨.
false일 경우도 마찬가지.

예를 들면, 세번째 노드에 찾는 데이터가 있다고 해 보자.
1. 첫번째 노드의 데이터와 찾고자하는 데이터가 맞는지 비교한다.
2. 아니니까 else문으로 넘어간다.
3. current->next가 널이 아니니까(다음 노드가 있으니까) 다음 노드에 대해 recursiveFind()를 재귀호출한다.
4. 다음 호출된 recursiveFind()에서는 2번째 노드가 current니까 2번째 노드의 데이터와 찾고자 하는 데이터가 일치하는지 비교
5. 역시 아니니까 else문으로 넘어가고,
6. current->next가 널이 아니니까 3번째 노드에 대해 recursiveFind()호출
7. 호출된 recursiveFind()에서는 3번째 노드 주소값이 current니까 3번째 노드의 데이터와 찾고자 하는 데이터가 일치하는지 비교
8. 일치하니까 true 리턴,
9. 이건 함수 속에서 함수를 콜했던 거니까 리턴해보니 아까 빠져나왔던 함수에서 받은 리턴값을 리턴하면 되네? 역시 true리턴
10. 여기도 마찬가지. true 리턴. 끝.

recursiveFind(head)
                     ->recursiveFind(다음노드)
                                                ->recursiveFind(다음노드)
                                                    찾았음!
                                                 <-return true
                       <-return true
<-return true

형태로 함수 콜이 이루어지겠지.

코드 라인을 하나 하나 따라가면서 머릿속으로 굴려보면서 이해해 보고, 사실 링크드 리스트는 unary tree로 생각해볼 수도 있으니
여기에서 변형하면 n-ary tree에서도 써먹을 수 있지.


여튼 끝