Page 165 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

05-1 재귀의 기본

05장에서는 재귀 알고리즘의 기본을 알아보겠습니다.

재귀란?

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이
라고 합니다. 그림 5-1은 재귀의 개념을 그림으로 표현한 예로, 화면 가운데에 다시 화면이

나타납니다. 그 화면 가운데에도 다시 화면이 반복되어 나타납니다. 이러한 재귀의 개념을 사
용하면 1부터 시작하여 2, 3, … 과 같이 무한하게 이어지는 자연수를 아래처럼 정의할 수 있
습니다.

1. 1은 자연수입니다.
2. 자연수 n의 바로 다음 수도 자연수입니다.

재귀적 정의(recursive definition)에 의해 무한으로 존재하는 자연수를 위의 두 문장으로 정의

할 수 있습니다. 재귀를 효과적으로 사용하면 이런 정의뿐만 아니라 프로그램도 간결하게 할
수 있습니다.
재귀는 06장에서 살펴볼 병합 정렬과 퀵 정렬, 10장에서 살펴볼 이진검색트리 등에 사용됩니다.

[그림 5-1] 재귀 개념을 표현한 예

05•재귀 알고리즘 165