: 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

void func1(int n) {
   if (n == 0) return ;
   printf("%d", n);
   func1(n-1);
}

n부터 1까지 출력하는 문제

이 코드가 왜 올바른 결과를 주는지 이해할 필요가 있다.

어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것인데, 이 귀납적인 방식은 우리의 상식과 큰 차이가 있다.

예를 들어 도미노에서 제일 앞의 도미노를 쓰러트리게 되면 모든 도미노가 쓰러진다. 그러나 . 왜모든 도미노가 쓰러지는 지를 설명해보라고 한다면 두 가지 방법이 있다.

첫 번째 설명 방법은 1번 도미노가 쓰러지면 2번 도미노가 쓰러지고, 2번 도미노가 쓰러지면 3번 도미노가 쓰러지고 ... 이런 식으로 계속 진행되기 때문에 모든 도미노가 쓰러진다는 설명 방법이다.

반면 두 번째 설명 방법은 수학적 귀납법을 이요한 방법이다. '1번 도미노가 쓰러진다, k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다' 가 참이니까 모든 도미노가 쓰러진다는 설명 방법이다.

앞으론 '1번 도미노가 쓰러진다', 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다' 까지만 생각한 후에 바로 모든 도미노가 쓰러진다는 결론에 도달할 . 수있어야 한다.

지금까지 당연하게 생각하던 절차 지향적인 사고를 탈피해야 한다.

다시 돌아와 func1 함수가 n부터 1까지 차례로 출력하는 함수임을 귀납적인 사고로 이해해보자

첫 번째로 func1(1)이 1을 출력한다, 이건 굉장히 자명하다. 그 다음이 관건인데 func1(k)가 k k-1 k-2 … 1을 출력하면, 즉 k부터 1까지 차례대로 출력하면 func1(k+1)은 k+1부터 1까지 차례로 출력한다는걸 보여야 한다.

이걸 보이는건 func1(k+1)이 호출될 때 어떤 상황이 생기는가를 보면 되는데 k+1이 출력된 이후 func1(k)가 호출되고 func1(k)는 k부터 1까지 차례로 출력한다 가정을 했으니 func1(k+1)은 k+1부터 1까지 차례대로 출력함을 알 수 있다.

이 두 문장이 참이므로 귀납적으로 func1 함수가 n부터 1까지 차례로 출력하는 함수임을 알 수 있게 된다.

올바른 재귀 함수는 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함. 이러한 입력을 base condition, base case 라고 한다.

그리고 모든 입력은 base condition 으로 수렴해야 한다.

재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨 (이 스택 영역은 메모리 구조에서의 스택 영역을 뜻함)

ps 문제를 풀 때 메모리 제한이 있음. 이 제한이 512MB라고 하면 프로그램이 점유하는 메모리가 최대 512MB여야 하는데, 일부 컴파일 환경에서는 스택 영역의 메모리가 별도로 1MB로 제한되어 있기도 함.

따라서 스택 메모리가 작게 제한된 곳에서 문제를 푸는데 풀이가 재귀를 깊게 들어가는 풀이라면 반복문으로 문제를 풀이해야한다.

곱셈 1629

1승을 계산할 수 있다.

k승을 계산했으면 2k승과 2k+1승도 O(1)을 계산할 수 있다.

#include <stdio.h>

long long POW(long long a, long long b, long long c)
{
    if (b == 1)
        return a % c;
    long long val = POW(a, b / 2, c);

    val = val * val % c;

    if (b % 2 == 0)
        return val;
    return val * a % c;
}

int main()
{
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);

    printf("%lld\n", POW(a, b, c));

    return 0;
}

b = 1일 때를 base condition으로 뒀는데 b = 0일 때로 두어도 상관없다. 그리고 a가 m보다 클 수 있기 때문에 a를 반환하는 대신 a % m을 반환해준다.

그 다음에는 재귀적으로 a^b/2 mod m을 계산해 val에 대입하고 val을 제곱했다. 만약 b가 7이라고 한다면 b/2는 3이니 09번 줄이 끝났을 때 val은 a6 mod m의 값이 들어갈 것이다. 즉 b가 짝수이면 그냥 val의 값을 반환하면 끝이지만 b가 홀수이면 val에 a를 한 번 더 곱해서 반환해야 한다.