재귀

어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것이다.

 

'제일 앞의 도미노를 쓰러트리게 되면 모든 도미노가 쓰러진다'는 전제가 존재할 때, 수학적 귀납법을 통하여 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다'는 생각을 한다면 문제를 재귀적으로 접근한 것이다.

 

아무튼 특정 메소드 내부에 메소드 자신을 호출하는 방식의 메소드가 곧 재귀 메소드인 듯 하다.

 

재귀 메소드의 조건

특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다. 이러한 특정 입력을 Base condition 내지는 Base case라고 부른다. 모든 입력은 Base condition으로 수렴해야 한다.

해당 조건이 없을 시 재귀 메소드는 결과를 내지 못하고 무한히 돌아가게 될 것이다.

 

참고 사항

• 메소드의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 한다.
• 모든 재귀 메소드는 반복문만으로 동일한 동작을 하는 메소드를 만들 수 있다.
• 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서는 손해를 본다.
• 한 메소드가 자기 자신을 여러 번 호출하게 되면 비효율적일 (이미 계산한 걸 또 계산하는 등) 수 있다. (ex. 피보나치)
• 재귀 메소드가 자기 자신을 부를 때 스택 영역에 계속 누적이 된다. (코테 문제의 메모리 제한과 스택 메모리 제한은 별개이다.)

 

연습 문제

 

1. 백준 1629 : https://www.acmicpc.net/problem/1629

 

a^n x a^n = a^2n 이므로 k승을 계산했으면 2k승과 2k+1승도 O(1)에 계산할 수 있다.

var input = Array.ConvertAll(Console.ReadLine().Split(), ulong.Parse);

ulong Pow(ulong a, ulong b, ulong c)
{
    if (b == 1) return a % c;
    ulong val = Pow(a, b/2, c);
    val = val * val % c;
    if(b%2 == 0) return val;
    return val * a % c;
}

Console.WriteLine(Pow(input[0], input[1], input[2]));

 

 

 

 

2. 백준 11729 : https://www.acmicpc.net/problem/11729

 

1. 메소드 정의 : 원판 n개를 a번 기둥에서 b번 기둥으로 옮기는 방법을 출력한다. void method(int a, int b, int n)
2. Base condition : n=1일 때 Console.WriteLine($"{a} {b}");
3. 재귀 식 : 
   1. n - 1개의 원판을 기둥 a에서 기둥 6 - a - b로 옮긴다. method(a, 6 - a - b, n - 1);
   2. n번 원판을 기둥 a에서 기둥 b로 옮긴다. Console.WriteLine($"{ a } { b }");
   3. n - 1개의 원판을 기둥 6 - a - b에서 기둥 b로 옮긴다. method(6 - a - b, b, n - 1);

using System.Text;
StringBuilder sb = new StringBuilder();
void method(int a, int b, int n)
{
    if (n == 1) { sb.Append(new string($"{a} {b}\n")); return; }
    method(a, 6 - a - b, n - 1);
    sb.Append(new string($"{a} {b}\n"));
    method(6 - a - b, b, n - 1);
}
var input = int.Parse(Console.ReadLine());
Console.WriteLine((1 << input) - 1);
method(1, 3, input);
Console.WriteLine(sb.ToString());

 

 

 

3. 백준 1074 : https://www.acmicpc.net/problem/1074

 

1. 함수의 정의 : 2^n x 2^n 배열에서 ( r , c )를 방문하는 순서를 반환하는 함수. int method (int n, int r, int c)
2. Base condition : n = 0일 때 return 0;
3. 재귀 식 : 
   1. ( r , c )가 1번 사각형일 때 return method(n - 1, r, c);
   2. ( r , c )가 2번 사각형일 때 return half * half + method(n - 1, r, c - half);
   3. ( r , c )가 3번 사각형일 때 return 2 * half * half + method(n - 1, r - half, c);
   4. ( r , c )가 4번 사각형일 때 return 3 * half * half + method(n - 1, r - half, c - half);

int method(int n, int r, int c)
{
    if (n == 0) return 0;
    int half = 1 << (n - 1);
    if (r < half && c < half) return method(n - 1, r, c);
    if (r < half && c >= half) return half * half + method(n - 1, r, c - half);
    if (r >= half && c < half) return 2 * half * half + method(n - 1, r - half, c);
    return 3 * half * half + method(n - 1, r - half, c - half);
}
var input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
Console.WriteLine(method(input[0], input[1], input[2]));