반복문과 재귀함수를 사용하며

🔃 재귀 함수 (Recursive Function)

재귀는 마치 ZAP에서 화면공유를 할 때 공유되는 화면을 공유하는 것과 비슷합니다.

• 함수가 직접 또는 간접적으로 자신을 호출하는 프로세스
• 구현 시 종료시점을 고려해야 함(스택오버플로 발생 가능성 고려)
• 장점: 코드의 길이가 짧고 구현이 간편함
  예시) 이진트리 순회

void printPreorder(TREE* current){
    //현재 트리 노드 출력
    fprintf(fout, "%d ", current->data);
    //왼쪽 트리 출력
    if (current->left_pointer!=NULL) {
        printPreorder(current->left_pointer);
    }
    if (current->right_pointer!=NULL) {
        printPreorder(current->right_pointer);
    }
    //오른쪽 트리 출력
}

void printInorder(TREE* current){
    if (current->left_pointer!=NULL) {
        printInorder(current->left_pointer);
    }

    fprintf(fout, "%d ", current->data);
    
    if (current->right_pointer!=NULL) {
        printInorder(current->right_pointer);
    }
}

void printPostorder(TREE* current){
    //왼쪽 트리 출력
    if (current->left_pointer!=NULL) {
        printPostorder(current->left_pointer);
    }
    //오른쪽 트리 출력
    if (current->right_pointer!=NULL) {
        printPostorder(current->right_pointer);
    }
    //현재 트리 노드 출력
    fprintf(fout, "%d ", current->data);
}

반복문으로 구현하려고 한다면 이보다 코드의 길이도 길어지고, 각각의 순회 방식을 변경하려 했을 때 수정해야 하는 부분도 많아질 것입니다. 이처럼 재귀적인 연산이 필요할 때에는 재귀함수를 이용했을 때 더욱 직관적이고 코드 수정이 간편한 코드를 작성할 수 있습니다.

반복문과 재귀함수

이 둘을 왜 비교하는지 의문이 들수도 있습니다. 사실 반복문과 재귀함수는 크게 공통점이나 차이점이 있지 않다고 생각하실 수 있기 때문이죠. 또한 모든 재귀함수는 반복문(while문)으로 구현이 가능합니다. 그럼에도 이 둘을 비교하는 이유는 비교를 통해 각각의 개념에 대해 제가 더 자세히 이해할 수 있었기 때문이에요.

같은 연산을 반복적으로 수행해야 할 때, 주로 for 문 또는 while 문을 사용하기도 하고, 또 한 가지 방법으로는 함수를 재귀호출하는 방법이 있어요. 사실 파이썬을 처음 배웠을 시점에는 함수를 재귀호출 하는 방식으로 반복적인 연산을 해결해야할 필요성에 대해 의문이 들었습니다.

그래프 이론에 대해 공부하면서 stack구조를 활용한 탐색 방법으로 재귀함수를 이용한다는 것을 알게 되었고, 단순히 반복적으로 연산을 처리하는 것이 아니라 연산을 처리하는 순서와 처리하는 시간에 차이가 있다는 것을 알게 되었어요.

자료구조적 관점에서 보면, 재귀호출은 단순히 데이터를 순차적으로 탐색하기 위해 사용한다기보다는 스택 구조를 사용하기 위해서 재귀호출을 수단으로 사용한다는 느낌을 받았습니다. 메모리의 스택 영역에서 스택프레임을 할당하고 삭제하는 방식이 Stack과 동일하게 작동하기 때문에 재귀함수를 이용하면 스택을 활용한 탐색, 예를 들면 DFS와 같은 알고리즘을 쉽게 구현할 수 있습니다.

또한 메모리구조와 함수 호출 과정에 대해 알아보며 이 둘의 차이점에 대해 생각해보았습니다. 반복문을 사용하는 것에 비해 함수를 재귀호출 하는 과정은 훨씬 더 많은 작업이 필요합니다. 함수 호출과 관련된 변수들이 스택 영역에 저장되고 함수가 종료되지 않은 상태에서 계속 재귀호출 될 경우 메모리의 스택 영역을 벗어나는 스택 오버플로우가 발생할 수 있죠. 이때 스택 프레임을 할당하고 삭제하는 과정에서 base pointer와 stack pointer 두 개의 레지스터로 함수 호출을 감당하기 때문에 반복문에 비해 느릴 수밖에 없는 것입니다.

제가 비전공자였기 때문에 이러한 고민을 시작하게 되었다고 생각합니다. 만약, 컴퓨터 구조에 대해 배웠고 메모리 구조나 함수 호출 과정에 대해 알고 있었다면, 반복문과 어떤 차이가 있는지에 대한 고민하게 되지 않았을 것 같아요.

하나의 예시일 뿐이지만, 비전공자가 좋은 코드를 작성하기 위해서는 기초적인 컴퓨터 지식에 대해 학습하는 것이 필수적이라는 것을 느꼈습니다.