[알고리즘] 재귀 함수란?

개요

알고리즘 풀이 과정 중에서 재귀함수를 어떤식으로 접근하여, 적용할 수 있는지에 대한 사례와 패턴을 기록합니다.

재귀에 대한 지식 정리

문제룰 정의하고, 문제를 풀기 위한 핵심 아이디어를 발견해내는 것이 중요하다.

코딩을 하기 전에, 문제를 정확하게 이해하고, 문제가 요구하는 바를 정확하게 파악하는 것이 중요하다.

문제를 보고 한눈에 이해되지 않고 감이 잡히지 않을 때, 아래의 질문과 함께 답을 적어보자.

Q1. 문제에서 요구하는 목표를 다른 말로 표현해보자.

<하노이의 탑 문제의 상황 및 조건>
- 세 개의 막대가 있다. => 막대의 수는 상수이므로 A, B, C로 추상화한다.
- 여러개의 원반이 있다. => 원반의 수는 입력 변수이므로, N으로 추상화한다.
- 원반은 크기가 서로 다르고, 원반 위에는 아래 원반보다 작은 원반만 올릴 수 있다.
- 원반은 한번에 한개씩만 움직일 수 있다.
=> 2개의 제약조건은 명확하게 추상화 하기 어렵다. 일단 과정을 나열하면서 무슨 말인지 이해해보자.
=> 원반의 크기는 무엇으로 추상화될 것인가? 재귀함수의 깊이..!

<하노이의 탑 문제의 유형>
유형 1) 아래 목표를 달성하기 위한 최소의 이동횟수로 옮기는 가짓수를 구해라
(효율성을 극대화하는 방법을 도출할 수 있는가?)
유형 2) 아래 목표를 달성하기 과정의 순서를 구해라
(과정을 추상화할 수 있는가?)

<하노이의 탑 문제의 목표>
N개의 원반이 주어졌을 때, 막대 "A"에 쌓여있는 원반들을 그 순서를 지키면서 (제약조건: 한번에, 순서대로) 그대로 "C"로 옮기는 것이다.
=> 추상화된 문자들로 목표를 재정의한다.

Q2-1. 문제의 정답이 해와 같이 답이 하나라면 X로 치환하여 접근해서, 문제의 조건들을 대입해보면 도움이 된다.

Q2-2. 문제의 정답을 도출하기 위해 필요한 입력과 출력을 가진 가상의 함수(F1, F2, F3...)들을 말로 표현해보자.

어떻게 구체화할지는 모르겠지만, 추상화 함수 F, subF... 으로 추상화 해본다.

<하노이의 탑 문제의 정답을 반환해주는 함수 F(N)>
F(N) : 원반의 개수(N)을 입력 받아, A 막대에서 C 막대로 옮기는 모든 움직임(Action)을 원반의 크기와 함께 출력해주는 함수

Q3-1. 추상화하기 어려울 경우, 과정을 그려보고 원하는 출력의 결과를 직접 입력해 봅니다.

1번 원반을 A => C로 이동
2번 원반을 A => B로 이동
1번 원반을 C => B로 이동
3번 원반을 A => C로 이동
1번 원반을 B => A로 이동
2번 원반을 B => C로 이동
1번 원반을 A => C로 이동

Q3-2. F(N)을 F(N-1)개로 표현할 수 있는지를 확인해 보고, F(N-1)이 없는 경우에는 어떻게 반활할 수 있는지 확인해봅니다.

F(N) {
    if (N == 1) {
        print(1 + '번 원반을' + 'A' + '막대에서' + 'B' + '막대로 이동');
    } else {
        F(N-1)...?
    }
}

Q3-3. F(N) 함수를 구체화 해봅니다.

F(N, A, B) { // F(N)함수에서 사용되는 변수에 해당하는 값들을 추가로 입력 인자에 추가
    if (N == 1) {
        print(1 + '번 원반을' + A + '막대에서' + B + '막대로 이동'); // 1은 애매한데?
    } else {
        F(N-1)...?
    }
}