[알고리즘] 재귀 - 귀납적 사고와 재귀 함수 구조 짜기

문제를 재귀 방식으로 푼다는 것은 귀납적 방식으로 문제를 해결하겠다는 것이다. 이 마인드가 상당히 중요한데, 재귀 문제를 일반 문제 풀듯이 절차 지향적으로 이해하면 안 된다.

 

예를 들어 1~N까지 출력하는 재귀 함수는 아래와 같이 구현할 수 있다.

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

이 함수를 절차 지향적으로 사고하면 3 출력 -> func1(2) 호출 -> 2 출력 -> func1(1) 호출 -> 1 출력 -> func1(0) 호출 -> 종료와 같은 방식으로 이해할 수 있다. 나도 계속 이런 방식으로 이해했었고 그래서 재귀가 두려웠다. 이번에는 귀납적으로 사고해 보자.

 

1. func1(1)은 1을 출력하고 종료된다.

2. func1(k)가 k, k-1,..., 1을 출력한다고 가정했을 때 func1(k+1)은 k+1을 출력하고 func1(k)를 호출하므로 k+1, k,..., 1을 출력한다.

 

이런 방식으로 이해할 수 있다. 또 도미노를 다른 예시로 들 수 있겠다. 도미노는 k번째 도미노가 쓰러진다고 가정하면 k+1번째 도미노도 쓰러진다. 이런 귀납적 사고를 가장 먼저 할 줄 알아야 하고 가장 중요하다!

 

이제 재귀 함수 구조를 짜야하는데, 몇 가지 팁이 있다.

 

1. 재귀 함수는 특정 입력에 대해 자기 자신을 호출하지 않고 종료하는 base condition이 있어야 하고, 모든 입력은 base condition으로 수렴해야 한다.

2. 재귀에서는 함수의 형태를 명확히 잡아야 한다. 함수의 형태란 함수의 인자나 어디까지 계산하고 자기 자신을 호출할 지등이다.

• 따라서 귀납적 사고 이후에 함수의 형태를 잡고 -> base condition을 설정하고 -> 재귀식을 설정하면 재귀 함수의 끝이다.

3. 모든 재귀 함수는 반복문으로 바꿀 수 있다. 거의 모든 케이스가 재귀 함수보다 반복문이 공간적, 시간적으로 이득이므로 재귀 없이 구현이 힘든 경우만 재귀로 풀자.

 

정리하자면 문제를 만났을 때 귀납적으로 사고가 가능하다면 재귀 팁들을 떠올리면서 구현해 보자! 귀납적 사고를 구현으로 옮기는 것도 사실 꽤 어려웠다. 충분히 많은 문제를 풀어봐야 한다.

 

아래의 추천 문제들을 꼭 풀어보자. 처음에는 30분 정도 고민해 보고 모르겠으면 귀납적 사고와 재귀 함수 구조 짜는 것을 참고하는 것을 추천한다.

[BOJ] C++ 1629 곱셈 - 귀납적 사고와 재귀 함수 구조 연습하기

 

[BOJ] C++ 11729 하노이 탑 - 재귀 함수 구조 짜기

 

[BOJ] C++ 1074 Z - 재귀