재귀 함수

재귀 함수

재귀(Recursion)란 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 말하며 재귀 함수란 함수 안에서 자기 자신을 호출하는 함수를 말한다. 재귀 함수는 짧은 코드로 재귀적인 작업을 수행하는 강력한 함수이지만 그 이해가 쉽지 않다. 이 글에서는 재귀 함수를 잘 쓰기 위해 3단계로 작성하는 법을 소개한다.

재귀 함수 4단계 작성법

재귀 함수를 꼭 써야하나?

재귀 함수로 풀수 있는 문제는 대부분 반복문으로도 풀 수 있다. 반복문이 재귀 함수보다 성능이 좋기 때문에 반복문으로 구현하는 것이 좋다. 따라서 재귀를 쓰기 전에 반복문으로도 풀 수 있는지 고민해보자.

 

1. (가장 중요) 재귀 함수를 작성하기 전에 재귀 함수가 어떤 일을 하고, 어떤 함수인지 명확히 정의한다. 이를 통해 아래 단계를 쉽게 진행할 수 있게 하며 각 재귀 함수가 서로 동등한, 평평한 구조임을 깨닫게한다. 처음 재귀를 접하면 재귀 흐름을 따라가는 사람들이 많은데 그럴 경우 재귀를 어렵게 사용하게 된다.

 

2. 베이스 조건

 

재귀 함수를 작성할 때 먼저 베이스 조건을 고려하자. 베이스 조건이란 재귀 함수의 종료 조건이다. 베이스 조건이 없으면 재귀 함수는 무한히 자기 자신을 호출하므로 베이스 조건은 필수다. 

 

3. 분해

 

베이스 조건을 작성했다면 그 다음 재귀 함수가 호출될 때마다 인자를 한 단계 더 간단해지도록 조작해 인자가 베이스 조건에 가까워지도록 한다. 이를 재귀적 분해(Recursive Decomposition)라고 한다. 이러다가 어느 순간 인자가 베이스 조건에 걸려 재귀 호출이 멈추게 된다.

 

4. 조합

 

재귀 함수에 반환 값이 있다면 조합 단계가 필요하다. 조합 단계는 부분 답(재귀 함수 반환 값)을 가지고 전체 답을 구하는 단계이다. 이때 부분 답은 무조건 정답이라고 가정한다. 이걸 재귀적 믿음의 점프(Recursive leap of faith)라 한다. 부분 답을 기반으로 전체 답을 구해 반환한다.

 

이런식으로 베이스 조건, 분해, 조합 순으로 재귀 함수의 코드를 작성해보자. 명심할 것은 우린 컴퓨터가 아니므로 재귀 흐름을 따라가지 말자. 그러면 재귀 함수를 어렵게 사용하게 된다.