[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- 재귀
- Q&A
- 마치며
1. 재귀(Recursion)
- 재귀(Recursion)
: 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘
예를 들어, 다음은 1부터 n까지 출력하는 함수, 1부터 n까지의 합을 구하는 함수입니다.
void func1(int n){
if(n == 0) return;
cout << n << ' ';
func1(n-1);
}
int func2(int n){
if(n == 0) return 0;
return n + func2(n-1);
}1) 수학적 귀납법
예를 들어 도미노를 쓰러뜨릴 때, 왜 모든 도미노가 쓰러지는지 설명해야 함
-
1번 도미노가 쓰러지면 2번도 쓰러짐 -> 2번이 쓰러지면 3번도 쓰러짐 -> ...
-
수학적 귀납법
1번 도미노가 쓰러짐 -> k번 도미노가 쓰러지면 k+1번 도미노도 쓰러짐이 True! -> 따라서 모든 도미노가 쓰러짐.
앞으로는 1번 방식이 아닌, 2번 방식으로 바로 사고할 수 있도록 해야 함.
(이전까지의 절차지향적 사고를 탈피해야 함!)
(1) 절차지향적 사고
다음은 위의 1부터 n까지 출력하는 함수.
void func1(int n){
if(n == 0) return;
cout << n << ' ';
func1(n-1);
}func1(3)을 호출하면 3을 출력하고 func1(2)를 호출함.
func1(2)를 호출하면 2를 출력하고 func1(1)을 호출함.
func1(1)을 호출하면 1을 출력하고 func1(0)을 호출함.
func1(0은 조건문에 의해 걸려, 함수가 종료됨.
따라서 출력은 3 2 1이 됨.
(2) 귀납적 사고
func(1)은1을 출력한다.
1번은 굉장히 자명함.
-
그 다음은
'func1(k)가k, k-1, k-2, ... , 1을 출력한다면,func1(k+1)가k+1, k, k-1, ... ,1을 출력한다'
는 것을 보여야 함. -
func1(k+1)을 호출하면,k+1을 출력하고func1(k)를 호출함.
이 때,func1(k)는 위의 가정에 의해,k ~ 1까지를 출력한다고 했으므로,
func1(k+1)은(k + 1) ~ 1까지 출력함.
앞으로 모든 재귀는, 1번과 같은 절차지향적 사고가 아닌, 2번과 같은 귀납적 사고로 이해해야 함.
2) 재귀 함수의 조건
- 재귀 함수의 조건
: 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함(Base Condition, Base Case)
: 모든 입력은 Base Condition으로 수렴해야 함.
void func1(int n){
if(n == 0) return;
cout << n << ' ';
func1(n-1);
}위의 코드에서, if문에서 n이 0이면 자기 자신을 호출하지 않고 종료됩니다.
따라서 이것이 Base Condition.
그리고 우리는 이 함수에 자연수만 넣을테니, 모든 입력은 n = 0(Base Condition)으로 수렴됨.
만약 이 두 조건 중 하나라도 지켜지지 않는다면, 재귀함수는 무한번 실행되다가 런타임 에러를 발생시킴.
3) 재귀에 대한 Tip
(1) 함수를 명확하게 정의한다!
정의라는 것은
-
함수의 인자로 어떤 것을 받는가
-
어디까지 계산한 후에, 자기 자신으로 넘겨주는가
를 의미함.
(2) 모든 재귀는 반복문만으로도 동일한 동작을 할 수 있다!
재귀는 상황에 따라 코드는 간결해지지만, 함수 호출 비용은 비용이 큰 연산이므로, 메모리와 시간에서 손해를 봄.
따라서, 재귀를 굳이 쓰지 않아도 되고 구현에 큰 어려움이 없으면 반복문으로 쓰는게 좋음.
하지만 반복문으로 구현했을 때 코드가 복잡해지면 재귀로 구현하는 게 나음.
(3) 재귀는 비효율적일 수 있다!
재귀 함수가 자기 자신을 여러 번 호출하면 예상과는 다르게 비효율적일 수 있음.
예를 들어 피보나치 수열을 재귀함수로 짜면, 시간복잡도는 지수함수 형태임
(n = 100만 되어도 2만년이 넘게 걸림)
그 이유는 다음과 같음.
fibo(5)를 할 경우, fibo(4), fibo(3)을 호출
fibo(4)를 할 경우, fibo(3), fibo(2)를 호출
fibo(3)를 할 경우, fibo(2), fibo(1)을 호출
그러면 fibo(4)에서 나온 fibo(3)을 계산하고, 또 fibo(5)에서 나온 fibo(3)을 다시 계산해야 함.
이미 다른 과정에서 계산한 값을, 또 다른 과정에서 다시 계산하는 일이 일어남.
(4) 재귀 함수가 자기 자신을 부를 때, 스택 영역에 계속 누적된다!
만약 문제를 풀 때, 메모리 제한이 512MB라면, 프로그램이 점유하는 메모리가 최대 512MB여야 함.
일부 컴파일 환경에서는 스택 영역의 메모리가 별도로 1MB로 제한되어 있기도 함.
BOJ에서는 스택 메모리 제한이 없지만, swexpertacademy에는 있음.
따라서 후자처럼 스택 메모리 제한이 작게 제한된 곳에서는, 재귀를 깊게 들어가는 풀이라면 반복문으로 변환해야 함...
4) 예시 - 하노이 탑
(1) 귀납적 사고
- n-1개의 원판을 기둥1에서 기둥 2로 옮긴다.
- n번 원판을 기둥 1에서 기둥 3으로 옮긴다.
- n-1개의 원판을 기둥2에서 기둥 3으로 옮긴다.
즉, 원판이 n-1개일 때 옮길 수 있으면 원판이 n개일 때도 옮길 수 있음.
귀납적 사고를 하면,
1. 원판이 1개 일 때 원하는 곳으로 옮길 수 있음.
2. 원판이 k개 일 때 원하는 곳으로 옮길 수 있으면, 원판이 k+1개 일 때에도 옮길 수 있음.
(2) 구현
(2.1) 함수의 정의
함수의 정의는, 함수가 어떤 역할을 수행하고 어떤 인자를 받는지 정하는 것.
void func(int n)위의 정의는 틀림!
왜냐 하면, 우리는 n-1개를 기둥1에서 기둥 3으로 옮기는 것이 아닌, 기둥2로 옮겨야 하기 때문.
void func(int a, int b, int n)원판 n개를 기둥a에서 기둥b로 옮기는 함수의 정의.
(2.2) Base Condition
n = 1일 때, a에서 b로 옮기면 됨.
(2.3) 재귀 식
- n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮김
func(a, 6-a-b, n-1);- n번 원판을 기둥a에서 기둥b로 옮김
cout << a << ' ' << b << '\n';- n-1개의 원판을 기둥6-a-b에서 기둥b로 옮김
func(6-a-b, b, n-1);참고로, 옮긴 횟수도 생각할 수 있음.
만약 원판 k + 1개를 옮길 때,
원판 k개를 옮기기 위해 x번,
원판 k+1번을 옮길 때 1번,
원판 k개를 다시 옮길 때 x번으로,
총 2X + 1번의 이동이 일어남.
더욱이 초항이 1이므로, 수열의 일반한은 2^k - 1이 됨.
2. Q&A
-
3. 마치며
-
[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
