티스토리 뷰
안녕하세요? 이화입니다. 현재 42서울 7기 1차 라 피신 진행중이신 분들은 dogkim이란 intra id로 조금 더 익숙하겠네요. 문제를 풀면서 새로운 걸 참 많이 배우게 되는데, 새로 배운 것과 원래 알던 것을 제 머릿속에서 글의 형태로 정리하면서, 피시너들을 포함한 다른 분들과 공유하기 위해 짧은 글 써 보게 되었습니다. 원래는 github site를 사용하는 블로그가 있었지만, 이번에는 부득이한 이유 블로그 테마가 영 맘에 안 들어서로 Tistory로 포스팅을 진행하고, 언젠가 블로그로 옮길 계획이에요.
참고로, 42서울과 직접적인 관련은 없는 내용입니다. 하지만 최대한 norminette 규정에 따르려고 노력한(테스트는 안 해봤다는 뜻입니다. 물론, 복사 붙여넣기하지 마세요. 문제 생기면 비공개합니다.) c코드와 write 함수가 사용되어 있어요. 모든 코드블럭은 실제로 실행되는 코드임을 보장하지 않으며, 헤더파일을 포함한 프로그램에 필수적인 부분이 생략되어 있습니다.
이 글은 다음에 해당하는 분들을 위한 글입니다.
- C언어의 기본적인 함수 개념을 알고 있다.
- 그런데 재귀?함수가 뭐에요? 어떻게 쓰는 거죠?
그리고 이 글은 다음 내용을 담고 있습니다.
- 재귀함수에 대한 기초적인 정의
- 재귀함수를 통한 문제 해결
자. 시작해 볼게요.
0. 너 자신을 알라! (Know Yourself!)
소크라테스의 명언입니다. 철학자들은 이 말이 "너 자신이 아무것도 모름을 인정해라" 라는 뜻이라고 합니다.
그렇지만, 이 내용은 본문과는 아무 상관 없습니다.
1. 재귀함수(recursive function)은 대체 무엇인가?
이 글을 읽는 여러분은 함수가 뭔지 알고 계실 거에요. 그럼 재귀? 재귀 함수가 뭘까요? 간단히 말해서, 재귀 함수는 함수 내부에서 자기 자신을 호출하는 함수입니다.
함수 안에서 함수를 호출하는 경험은 누구나 해 보셨을 거에요. 출력을 위한 write 함수나 printf함수, 아니면 또 다른 함수. 직접 만든 함수들을 말이죠. 그런데, 함수가 자기 자신을 호출한다니, 얼핏 보면 불가능해 보이잖아요? 하지만 이게 가능하다는 게 핵심입니다. 그리고 활용을 위해서는 이게 어떤 의미인지도 정확히 아셔야 해요.
간단한 함수를 하나 만들어 볼게요.
void f()
{
write(1, "Hello!", 6);
f();
}이 함수는 정말 간단해요. 첫 번째 줄에서 Hello!를 출력합니다. 두 번째 줄에선 자기 자신을 다시 호출합니다. 그럼 어떻게 될까요? 다시 f()의 첫 번째 줄을 실행하러 갑니다. Hello!를 출력하고 다시 자기 자신을 호출합니다. 다시 f()의 첫 번째 줄로... 다른 조건이 없기 때문에 무한히 반복합니다. 그렇지만, 함수의 처음으로 돌아간다면 반복문과 똑같이 작동하는 게 아닌가요? 하고 물으신다면 확실한 차이가 있습니다. 왜냐하면 함수는 호출될 때마다 메모리에 새 공간을 만들기 때문에, 정확히 말하자면 새로운 f()의 첫 번째 줄을 실행하러 가게 되기 때문입니다. 그리고 그렇기 때문에, 재귀함수라는 게 여러 가지로 응용되어 동작할 수 있는 거에요.
직관적으로 이해가 안 간다면 이렇게 이해해 주세요. 자기 자신을 호출하는 함수가 아니라, 결국 자기의 복사본을 호출한다. (정확한 설명은 아닙니다. 호출 스택에 대해 한번 검색해 주세요)
그럼 이번엔 무한히 반복하지 않게 만들어 볼까요?
void f(int d)
{
if (d == 0)
{
return;
}
write(1, "Hello!", 6);
f(d - 1);
}이 함수는 위 함수를 약간 개조해봤어요. 인자를 하나 받죠? 깊이를 뜻하는 depth의 d입니다. 그리고 첫째 줄의 if문은, d가 0이면 return합니다. void 함수에서의 return은 함수를 끝낸다는 의미를 담고 있어요. 그럼 이게 무슨 의미가 있죠? 계속 봅시다. 다음 줄은 여전히 Hello!를 출력하네요. f(d - 1);은 뭘까요? 숫자만 하나 줄여서 다시 호출하네요?
직접 실행시켜 보기 전에 컴퓨터가 실행하는 것처럼 생각해보는 건 매우 유용합니다. 한번 해 볼까요? f(3)을 호출하면 어떻게 될까요? f(3)에서 if문은 무시되고 Hello!를 출력하고 f(2)를 실행합니다. f(2)에서 if문은 무시되고 Hello를 출력하고 f(1)을 호출합니다. f(1)에서 if문은 무시되고 Hello를 출력하고 f(0)을 실행합니다. f(0)에서 드디어 if문이 실행되어서 기나긴 고리가 끝났습니다. 이렇게 총 3번 Hello를 출력했네요. 하지만 이 정도는 반복문이 낫습니다. 아까 말했던 것처럼 재귀함수는 자신의 복사본을 호출하기 때문에, 일정 횟수 이상 반복하면 메모리가 모자라지기도 하고, 속도도 느려요.
2. 재귀함수를 어떻게 써야 하는가?
사실상 핵심적인 챕터라고 할 수 있습니다. 반복문에 비해서 재귀 함수의 강점이 무엇인가? 그건 바로 나눠서 정복(Devide & Conquer)전략에 있다고 할 수 있습니다. 여러 문제를 작게 쪼개서 해결할 수 있다는 거죠. 이때, 주의해야 할 건 다음과 같습니다.
- 기저(bases)가 있어야 합니다. 더 이상 쪼갤 수 없거나 그럴 필요가 없는 기저에 도달하면 프로그램이 종료됩니다.
- 어떤 문제를 여러 개로 쪼갤 수 있어야 합니다.
- 쪼갠 문제의 결과를 조립해 원래 문제를 풀어낼 수 있어야 합니다.
여기서 제일 많이 쓰는 예시라면 단연 피보나치 수열일 것입니다. 피보나치 수열은 첫 번째와 두 번째가 1, 그 다음부터는 이전 항과 이전 항의 이전 항의 합입니다. n번째 피보나치 수열은 n-1번째와 n-2번째의 합으로 표현할 수 있고, 이를 반복함으로써 첫 번째와 두 번째의 합으로 모두 표현할 수 있습니다. 다음 그림을 봐 주세요.
그럼, 이걸 재귀함수로 만들어 볼까요?
int fibo(int n)
{
if (n == 1 || n == 2)
{
return (1);
}
return (fibo(n-1) + fibo(n-2))
}좀 감이 오시나요? 둘로 나누고 나누고... 새 함수가 호출될때마다 가지를 쳐 나가고, 다시 더함으로써 결과가 나옵니다. 이렇게 가지를 쳐 나갈 수 있다는 점을 잘 생각하고, 응용해서 가지를 세 개 네 개, 또는 가변적인 개수의 가지를 쳐 나갈 수도 있습니다. 하지만 그렇게 코드가 복잡해 보이지 않죠?
누군가 재귀함수를 한 편의 시라고 그러던데, 저는 되게 맘에 드는 표현입니다. 코드가 매력적이라고 해야할까요? 간결하고 이해하면 직관적인 코드를 작성할 수 있습니다. 모든 문제에 적용할 수 없지만, 나누고 조립할 수 있는 문제라면 웬만해선 풀 수 있습니다. 글은 여기서 끝입니다. 더 많은 예제를 수록하는 건 큰 의미가 없겠네요.
어째 글 내용이 뒤로 갈수록 단순해진다면, 제가 1시부터 2시까지 밤새 작성하는데 생각보다 오래 걸려서 빨리 자고 싶기 때문입니다. 내용은 언젠가 보강하거나, 다시 쓸 수도 있겠죠. 도움이 되셨다면 좋겠습니다. 궁금하신 내용은 피시너분들이라면 제 슬랙, 아니시라면 트위터 계정 으로 연락주시면 재빠른 대답 드리겠습니다. 읽어주셔서 감사합니다.
-1. 덤
관련해서 더 찾아보고 싶으신 분은, 다음 키워드로 검색해보세요. 제가 관련 글을 쓰게 된다면 링크하겠습니다.
- 재귀함수를 이용한 조합(Combination) 구현은 DFS와 관련이 있습니다(사실 DFS쪽이 더 복잡한 개념이라, 찾아보시게 된다면 좀 어려울 거에요.)
- 재귀함수의 최적화를 위해선 메모이제이션 또는 다이나믹 프로그래밍을 찾아보세요. 사실 둘 다 같은 겁니다.
- 재귀함수의 또 다른 최적화 기법으론 꼬리재귀가 있습니다. 방법은 간단하지만 원리는 호출 스택을 아셔야 합니다.
- 재귀함수로 구현할 수 있는 대표적인 문제를 원하신다면, 하노이의 탑 문제, 최소공약수 문제를 찾아보세요.