Algo 04 - 재귀함수란 무엇인가?

재귀 함수

알고리즘 글 순서에 있어서 사과드립니다...

어떤 나쁜 놈이 에라토스테네스의 체 뒤에 DAG을 넣을 생각을 했을까요... 죄송합니다.

다시 쉽게 맞춰 가기 위해서 기본 적인 재귀 함수 이야기를 하려고 합니다.

난이도는 별 2개 정도?

많은 분들이 재귀 함수에 대해서 어렵다는 생각을 가지고 있거나 실무에서 사용할 수 없는데 왜 자꾸 재귀 함수 거리냐고 생각할 수 있습니다.

여러분을 고통받게 하기 위해서 가 아니라...

• 아.. 장담은 못하겠네요. 워낙에 알고리즘 하는 사람들이 변태들이라 고통받는 걸 좋아하는 걸지도.. 너도 당해봐라? 이런?

사실 귀납적 추론 능력을 물어보고자 하는 것입니다.

왜 재귀 함수 거리는데 귀납적 추론 능력을 들먹이는 걸까요?

define

여러분은 귀납적 추론 문제를 학창 시절 어렴 풋이 배웠습니다.

1일 때 맞고 n일 때도 맞고, n+1일 때도 맞다면 이는 맞는 행동이다.

재귀 함수도 같습니다.

1일 때 함수가 제대로 작동하는지 생각하고 임이의 N인 상태에서도 정의가 맞고 N+1 상태 혹은 N과 다른 상태에서도 맞게 동작한다면 이 함수는 옳게 작성된 재귀 함수입니다.

이처럼 행동에 대한 정의를 만들어 주시면 됩니다.

물론 중요한 한 가지 요소를 고려해 주셔야 합니다.

기저 조건이라고 불리는 종결 조건입니다.

재귀 함수가 어느 순간에는 멈춰야 하는데 이 시점에 대한 정의를 하셔야 합니다.

• 안 하시면.. 뭐.. 무한 정도는 거죠.. 프로그램 터질 때까지 펑~

문제 1

https://www.acmicpc.net/problem/10870

대표적인 피보나치 문제입니다.

피보나치의 정의는 f(n) = f(n-2) + f(n-1 )입니다.

자 그럼 재귀 함수를 짜 봅시다.

저는 우선 기저 조건을 생각합니다.

언제 멈추어야 할까.. n을 입력받았을 때, 문제에서도 N>=2라고 주어져 있으니, f(2) = f(1) +f(0) :: f(2) return 1이니 2에 도달하면 1을 주고 끝내자 라고 생각하실 수 있습니다. 근데 조금만 더 생각하면 우리는 2를 입력받을 수 있고 그러면 f(1)과 f(0)을 호출하게 됩니다. 그러니 N이 1 이 되면 1을 0 이 되면 0을 반환하는 조건을 기저 조건으로 합시다.

if(n==1) return 1;
if(n==0) return 0;

자 그다음 할 일은 행동에 대한 정의인데 이문제는 행동을 이미 알려주고 있습니다.

f(n) = f(n-1) + f(n-2)

int func(int n){
    int ret = func(n-1)+func(n-2);
    return ret;
}

이제 두 가지를 합쳐주면

int func(n){
    if(n==1) return 1;
    if(n==0) return 0;
    int ret = func(n-1)+func(n-2);
    return ret;
}

///////////////

#include <iostream>
using namespace std;

int func(int n){
    if(n==1) return 1;
    if(n==0) return 0;
    int ret = func(n-1)+func(n-2);
    return ret;
}

int main(){
    int n;
    scanf("%d", &n);
    printf("%d", func(n));
    return 0;
}

문제 2

자 이제 행동을 정의하기 좀 더 어려운 하노이 탑 문제입니다.

https://www.acmicpc.net/problem/1914

종결 조건을 찾기 쉽죠.

간단하게 제일 작은 원판이라면 내가 원하는 곳으로 옮기면 되는 겁니다.

func(num, from, to) {
    if(num == 1 ) move(from, to)
}

//의미만 나타내기 위한 코드입니다.

어떻게 행동을 정의해야 할까요. 사실 하노이 탑에서 행동을 정의하신다면 정말 똑똑하시거나 경험이 많으신 건데 왜냐하면 상태를 정의할 줄 알아야 해요. via라는 어디를 통해서 간다라는 상태를 찾아서

원판의 개수, 시작점, 도중에 방문하는 곳, 도착점 이러한 변수로 상태가 정의될 수 있구나 하는 걸 생각하기가 참 어려워요.

그러니 여기서는 간단의 행동을 정의해주면 재귀 적으로 작동하는구나 감을 익히시면 되겠습니다.

func(cur, from, via, to) { // 원판 3개를 1에서 2를 거쳐 3으로 옮길꺼야!
    func(cur-1, from, to, via); // 그전에 원판 2개를 1에서 3을 거쳐서 2로 옮길 꺼야!
    move(cur to move); //원판 2개가 1에서 2로 갔으니 3원판은 이제 3번재에 옮기면 되지!
    func(cur-1, via, from, to); // 이제 원판 2개는 2에 있으니 1을 통해서 3번에 옮기면 되는군!
}

저렇게 행동에 대한 정의만 하시면 나머지는 재귀적으로 작동합니다.

약간 이게 무슨 소리야? 하실 수 있는데

원판 2개일 때 손으로 구해 보시 3일 때도 구해보세요. n일 때 n+1 때도 맞으면 맞는 행동입니다.

이렇게 귀납적으로 행동에 대한 정의만 구한다면 답이 안보이던 문제가 짧은 코드로 풀리는 걸 볼 수 있습니다.

풀 코드는 문제 번호 + 문제 이름 검색하시면 많이 제공되니 생략하겠습니다.

다시 말하지만 하노이탑은 혼자 생각해서 행동에 대한 정의를 하기 굉장히 어려운 문제입니다. 그러니 행동의 정의로 정말 짧은 코드로 해답을 구할 수 있구나만 알고 가시면 됩니다.

정리

귀납적으로 기저 조건 + 행동 정의로 복잡한 문제를 사실 간단하게 풀 수 있게 하는 게 재귀 함수다.