[알고리즘] 재귀(Recursion)와 수학적 귀납법(Mathematical Induction)

재귀(Recursion)

void func1(int n) {
    if (n == 0) return;
    cout << n << ' ';
    func1(n-1);
}
// func(4)의 결과
// 4 3 2 1

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

 

 

수학적 귀납법(Mathematical Induction)

• 재귀함수 코드가 복잡해진다면 재귀함수를 따라 들어가서 일일히 확하는 방법은 불가능에 가깝다.
• 수학적 귀납법을 이용해 정확성을 증명해야한다. 
• 어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결 하는 것이다.

 

 

위 사진의 도미노에서 제일 앞의 도미노를 쓰러트리게 되면 모든 도미너가 쓰러질 것이다. 이를 설명할 수 있는 방법은 두 가지가 있다.

맨 앞에서 부터 1번, 2번, 3번, ...  , n번 도미노라고 하자.

 

 

n부터 1까지 출력하는 재귀 함수

void func1(int n) {
    if (n == 0) return;
    cout << n << ' ';
    func1(n-1);
}

 

<절차지향적 사고>

 

<귀납적 사고>

절차지향적인 사고는 단순히 따라가기만 하면 되기때문에 이해가 쉽다. 귀납적 사고로 이해를 해보자.

첫번째로 1) 'func1(1) 이 1을 출력한다.'(base case) 이건 굉장히 자명하다. 그 다음 2) 'func1(k) 가 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까지 차례로 출력함'을 알 수 있다.

 

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

 

 

재귀 함수의 조건

올바른 재귀 함수는 반드시 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다.

이러한 입력을 base condition 또는 base case라고 한다. 그리고 모든 입력은 base condition으로 수렴해야 한다.

코드에서 n = 0일 때 종료가 되니 이것이 base condition이고 우리는 n 값으로 자연수만 넣을테니 모든 입력은 결국 n = 0으로 수렴한다.

두 조건 중 어느하나라도 지켜지지 않으면 재귀 함수는 결과를 내지 못하고 무한히 들어가다 Runtime Error가 발생하게 될 것이다.

 

• 재귀에서는 함수를 명확하게 정의해야 한다.
  • 함수의 인자로 어던것을 받을지?
  • 어디까지 계산 후 자기 자신에게 넘겨줄지?
• 모든 재귀 함수는 반복문으로 동일한 동작을 하는 함수를 만들 수 있다.
  • 재귀가 반복문 보다 코드가 간결해진다.
  • 함수 호출이 비용이 큰 연산이기 때문에 메모리와 시간에서는 손해를 본다.
  • 재귀 없이 구현에 큰 어려움이 없으면 반복문으로 코드를 짜는게 좋지만 코드가 너무 복잡해지면 재귀로 구현.

 

비효율적인 재귀함수 (피보나치함수)

int fibo(int n) {
    if (n <= 1) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

재귀 함수가 자기 자신을 여러 번 호출하게 된다면 굉장히 비효율적일 수 있다.

위 함수는 n번째 피보나치 수열을 반환하는 함수인데, 피보나치 함수는 초항 2개가 1 1이고 그 뒤의 항들은 직전 항 2개의 합으로 정의 된다.

 

base condition은 n이 1이하일 때이고 모든 입력에 대해 base condition으로 수렴할 것 이다.

그런데 이 재귀 함수의 시간 복잡도는 O(1.618^n)이다. n = 100 이라면 일반 컴퓨터로 약 20000년 넘게 걸릴 것 이다.

 

fibo(5) 계산 과정

fibo(5)를 예시로 들어보자. fibo(5)는 fibo(4)와 fibo(3)을 호출하고 fibo(4)는 fibo(3)과 fibo(2)를 fiibo(3)은 fibo(2)와 fibo(1)을...

여기서 중요한 점은 이미 계산한걸 또 계산하는 일이 아주 빈번함을 알 수 있다. 이렇게 이미 계산한 값을 다시 계산하는 일이 빈번하게 발생해서 시간 복잡도가 말도 안되게 커져버린다. 이와 같이 한 함수가 자기 자신을 여러번 호출할 경우에는 시간 복잡도가 매우 커져버릴 수 있다는 점을 조심해야한다.

 

*피보나치 문제의 경우에는 다이나믹 프로그래밍(Dynamic programming)이라는 방법을 이용해서 O(n)에 해결할 수 있다.

 

 

 

 

 

 

재귀 함수가 자기 자신을 부를 때 스택 영역에 함수에 대한 정보가 누적된다.

 

이 스택영역이라고 하는 것은 메모리 구조에서의 스택 영역을 말한다.

 

스택 메모리가 작게 제한된 곳에서 알고리즘 문제를 재귀로 풀게 된다면 런타임 에러가 발생하기도 한다.

 

 

 

 

 

 

 

 

 

<참고자료>

kimsungyoon-kok.github.io/blog/datastructure-0202/

ko.wikipedia.org/wiki/%EC%88%98%ED%95%99%EC%A0%81_%EA%B7%80%EB%82%A9%EB%B2%95

baaaaaaaaaaaaaaaaaaaaaaarkingdog.tistory.com/943?category=773649