재귀란?

러시아 인형을 본 적이 있나요? 처음에는 색칠된 나무 인형 하나만 보일 것입니다. 다음 그림처럼 생겼죠.

첫 번째 인형의 윗쪽 반을 들어서 열 수 있습니다. 무엇이 보이시나요? 약간 작은 또 다른 러시아 인형이군요!

그 인형을 꺼내서 위아래를 분리해서 열어 봅니다. 그럼 조금 더 작은 또 다른 인형이 나오는군요.

다시 한 번 해보죠.

계속 반복합니다. 결국 가장 작은 러시아 인형이 나왔군요. 이것은 다른 것들처럼 열리지 않네요.

처음에는 하나의 큰 러시아 인형으로 시작해서 점점 더 조그만 인형이 나왔죠. 인형이 너무 작아서 다른 인형을 담지 못하게 될 때까지 말이죠.

러시아 인형과 알고리즘 간에 어떤 상관관계가 있을까요? 러시아 인형 속에 더 작은 러시아 인형이 있고 또 그 인형 안에 더 작은 인형이 있는데, 이는 러시아 인형이 너무 작아서 다른 인형을 담지 못할 때까지 계속 됩니다. 이처럼 어떤 문제를 해결하기 위해 알고리즘을 설계할 때 동일한 문제의 조금 더 작은 경우를 해결함으로써 그 문제를 해결하는 것입니다. 문제가 간단해져서 바로 풀 수 있는 문제로 작아질 때까지 말이죠. 이런 테크닉을 재귀라고 합니다.

재귀는 다양한 문제에 적용할 수 있습니다. 이 모듈에서는 팩토리얼 함수를 계산하고, 어떤 단어가 회문(palindrome)인지 확인하고, 특정 수의 거듭 제곱을 계산하고, 특정한 프랙털을 그리고, 하노이의 고대 탑 문제를 해결하는데 어떻게 재귀법을 활용하는지 알아보겠습니다. 그 후의 모듈에서는 재귀법을 활용하여 정렬을 포함한 다른 문제를 풀어보겠습니다.

위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.