재귀함수 (Recursive Function)
쉽게 풀면
놀이공원에서 긴 줄을 서 있는데 내가 몇 번째인지 궁금하다고 해봅시다. 바로 셀 수 없으니 앞사람에게 "당신은 몇 번째예요?"라고 묻고, 그 사람도 또 자기 앞사람에게 똑같이 묻습니다. 이 질문은 맨 앞사람(더 이상 물을 사람이 없는 사람)에게 닿을 때까지 계속되고, 맨 앞사람이 "저는 1번째예요"라고 답하면 그 대답이 뒤로 하나씩 전달되며 각자의 순번이 정해집니다. 이렇게 "같은 질문을 더 작은 대상에게 반복해서 던지다가, 가장 단순한 경우에 이르면 답을 시작으로 거슬러 올라오는" 구조가 바로 재귀함수입니다. 재귀함수는 반드시 더 이상 자기 자신을 호출하지 않고 답을 바로 내놓는 "종료조건(base case)"을 가지고 있어야 합니다.
왜 중요한가
재귀함수는 트리, 그래프처럼 자기 자신과 같은 구조가 하위 단위에 반복적으로 나타나는 데이터를 다루는 알고리즘을 표현하는 가장 자연스러운 방법입니다. 정렬, 탐색, 분할정복 알고리즘의 설계부터 프로그래밍 교육에서 문제해결력을 기르는 소재까지 폭넓게 쓰이며, 재귀적 사고 자체가 이후 동적계획법이나 함수형 프로그래밍을 이해하는 기초가 되기 때문에 컴퓨터과학 교육·알고리즘 논문에서 빠짐없이 다뤄집니다.
논문에서는 이렇게 쓰입니다
이 문장은 트리처럼 같은 구조가 반복되는 데이터를 다룰 때, 하나의 함수가 자기 자신을 반복 호출해 하위 구조까지 일관되게 처리했다는 뜻입니다. 컴퓨터교육이나 알고리즘 관련 논문에서는 이처럼 기본 개념을 배경지식으로 언급한 뒤 본 주제로 넘어가는 경우가 많습니다.
프로그래밍 교육 연구에서는 재귀함수가 학습자들이 특히 어려워하는 개념으로 자주 다뤄지며, 이를 어떻게 효과적으로 가르칠지가 중요한 연구 주제입니다.
알고리즘 논문에서는 큰 문제를 작은 부분 문제로 쪼개어 재귀적으로 해결하는 분할정복 전략을 설명할 때 재귀함수라는 표현이 자연스럽게 등장합니다.
조금 더 깊게 보면
재귀함수는 크게 자기 자신을 한 번만 호출하는 선형 재귀와, 두 번 이상 호출하는 트리형 재귀(예: 피보나치 수열의 단순 재귀 구현)로 나눌 수 있는데, 트리형 재귀는 같은 계산을 여러 번 반복하는 비효율이 생기기 쉬워 이를 개선하기 위해 메모이제이션이나 동적계획법을 함께 적용하는 경우가 많습니다. 또한 함수 호출이 함수의 맨 마지막 동작으로만 이루어지는 꼬리재귀(tail recursion)는 일부 언어나 컴파일러에서 반복문과 동등한 수준으로 최적화될 수 있어, 스택 오버플로 위험을 줄이는 실용적인 기법으로 언급됩니다.
주의할 점
재귀함수에 종료조건을 넣지 않으면 함수가 자기 자신을 무한히 호출하다가 프로그램이 멈추거나 오류가 납니다(스택 오버플로). 재귀 호출이 거듭될 때마다 함수의 실행 정보가 스택과 큐의 스택 구조에 차곡차곡 쌓였다가 되돌아 나오는 순서로 처리된다는 점도 함께 이해해야 합니다.