재귀도 정말 어려운 파트였다. 단순하게 한 번씩 반복되는 게 아닌 퀵 정렬이나 하노이탑처럼 한 함수 안에 2개 이상의 재귀 혹은 조건들을 통해 실행하는 재귀 등 엄청 복잡했는데 이 부분을 잡아가도록 한다.
1. 재귀란?
재귀는 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘을 의미한다.
귀납적 사고
먼저 재귀를 제대로 이해하고 다루기 위해서는 귀납적인 사고방식을 가질 필요가 있다. 도미노를 예시로 설명해 보자.
먼저 도미노의 간격이 일정할 때 맨 앞 도미노가 쓰러지면 그다음 도미노가 쓰러지면서 최종 도미노까지 쓰러짐을 알 수 있을 것이다. 이 부분이 바로 귀납적인 사고이다.
1번 도미노, 2번 도미노, 3번 도미노 ... n번 도미노까지 모든 도미노가 쓰러지는 과정을 다 보는 게 아닌 다음과 방식으로 정리가 되기 때문이다.
- 1번 도미노가 쓰러진다.
- k번 도미노가 쓰러지면 k+1 도미노도 쓰러진다.
즉, 1번 도미노가 쓰러지면 n번 도미노까지 모두 쓰러진다.
이처럼 모든 과정을 추적하지 않고도 결론에 도달할 수 있다.
이해를 돕기 위해 더 예시를 들어보자.
다음 코드에 대하여 절차지향적인 사고와 귀납적 사고로 해석할 수 있다.
- 절차지향적 사고
1) n을 출력하고 func1(n-1)를 실행한다.
2) n-1을 출력하고 func1(n-2)를 실행한다.
n) 1을 출력하고 func1(0)을 실행한다.
- 귀납적 사고
1) func1(1)은 1을 출력한다.
2) func1(k)은 k, k-1, k-2, ..., 1을 출력한다면 func1(k+1)은 k+1, k, k-1, ..., 1을 출력한다.
위 두 방식의 차이가 이해가 됬다면 어느 정도 귀납적 사고에 적응이 됐다 볼 수 있다. 절치자향적 사고의 경우 func1(n)을 구하기 위해서 함수 내부와 그다음 재귀를 파고파고 들어가는 부분이지만, 귀납적 사고의 경우 이전 결과를 바탕으로 전체 흐름을 간단히 이해한다.
마지막으로 도미노를 정리해 보자면
n번째 도미노가 쓰러졌다. -> n-1번째 도미노가 쓰러졌다. -> ... -> 2번째 도미노가 쓰러졌다. -> 맨 처음 도미노가 쓰러졌다. 처럼 모든 과정을 파악해야 하는 절차지향적 사고가 아닌
- 1번 도미노가 쓰러졌다.
- k번 도미노가 쓰러지면 k+1 도미노도 쓰러진다.
따라서 f(n) = n + f(n-1)의 결과로 해석
즉 이전 결과를 바탕으로 전체 과정보다 결과에 집중한다.
재귀 함수의 조건
앞에서 설명한 귀납적 사고를 통해서 어느 정도 재귀 동작방식을 이해했다. 그러면 재귀 함수를 작성하기 위해선 반드시 base case(= base condition)이 존재해야 한다.
base case는 재귀가 자기 자신을 호출하지 않고 올바르게 종료되도록 설정하는 조건을 의미한다.
이제 그러면 재귀를 잘 이해하고 사용하기 위해서는 다음과 같이 재귀의 특성을 알아볼 필요가 있다.
2. 재귀 특성
재귀는 말 그대로 자신의 함수를 다시 호출해서 사용하는 방식이기 어찌 보면 단순히 반복문으로 대체도 가능할 것이다.
그러므로 재귀의 특성을 잘 이해한 뒤 상황에 맞게 재귀 특성을 생각하여 적용해 볼지 고민을 해보면 좋겠다.
- 함수의 인자와 어디까지 계산 후 자신을 넘겨줄지 명확히 해야 함
- 모든 재귀는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음
- 코드는 간결하지만, 반복문 구현에 비해 메모리/시간에서는 손해를 봄
하나씩 집어보자. 당연하게도 재귀는 행위를 반복하는것 이기때문에 함수 인자 설정과 계산 범위를 명확히 설정해야한다.
또한 반복하여 값을 도출하는 것이기 때문에 반복문으로도 구현이 가능해야한다.
마지막으로 코드는 간결해지나 함수를 호출하는 비용은 꽤 비용이 큰 연산이므로 메모리와 시간적인 측면에서 손해를 본다.
위 내용들을 꼭 숙지하여 반복문을 사용하지 않고 구현할 때 복잡해져서 재귀를 써야 한다면 위 내용을 꼭 고려해 보고 구현하자.
재귀의 비효율
재귀는 상황에따라 굉장히 비효율적일 수 있다.
다음은 재귀를 사용하면 안 되는 대표적인 예시인 피보나치이다.
피보나치는 초항 2개가 1, 1이고 뒤의 항들은 직전 항 2개를 더한 합으로 정의되는 함수이다.
위 함수를 사용하면 결국 1 이하일 때 1을 반환하는 base codition을 통해 결과가 잘 나올 것이다.
그러면 뭐가 문제냐? 눈치를 챘을 순 있지만 이미 구한 값을 또 계산하는 문제가 생긴다는 것이다.
당장 fibo(3)를 보면 f(2) + f(1)를 실행하는데 f(2)에서는 또 f(1) + f(0)로 f(1)를 또 계산한다는 것이다.
이 재귀함수의 시간복잡도는 O(1.618^n)이며 100만 돼도 컴퓨터가 2만 년이 넘게 걸릴 수 있다고 한다.
해당 문제는 다이나믹 프로그래밍 방법을 이용해 풀어갈 것이지만 위와 같이 재귀로 자기 자신 함수를 여러 번 호출하는 게 굉장히 비효율적일 수 있음을 알아야 한다.
스택 영역에 누적
재귀 함수가 자신 함수를 호출할 때 스택 영역에 계속 누적이된다.
아마도 운영체제나 자료구조수업에서 접했던 메모리 구조인데 지금은 기억이 가물가물하여 나중에 복습을 꼭 해야겠다.
재귀 함수가 자기 자신을 호출하면 스택 영역에 함수의 정보가 누적된다. 문제를 풀면 보통 메모리 제한이 존재할 텐데 컴파일 환경과 영역에 따라 스택 영역의 메모리가 별도로 1MB로 제한되어 있을 수 있다. 그렇다면 이게 어떤 문제냐 당장 int arr[1000][1000]의 배열을 지역 변수로 잡았다면 재귀를 실행할 시 4byte * 1000 * 1000 = 4,000,000byte -> 4MB가 되어 스택 영역을 초과한다.
물론 코테에서도 중요한 얘기지만 게임을 개발할 때 요즘 컴퓨터 사양이 좋아졌다 한들 어느 부분에서 병목현상이 발생할 때 해결할 수 없는 주요한 기능이라고 가정한다면 이런 메모리 영역 하나하나 무시할 부분이 못 된다.
그러므로 재귀를 사용하는 것은 메모리/시간 측면에서도 비효율적일 수 있으니 고려를 해봐야 한다.
3. 예시 문제(코드)
나머지 구하기
a,b,m에 대하여 a를 b승한 후 m으로 나눈 나머지를 구하는 문제를 풀 것이다.(= a^b mod m)
위에는 해당 문제에 대한 풀이인데 만약 (6,100,5)를 넣으면 어떻게 될까?
6을 5로 나누면 나머지가 1이니 당연히 6^100을 하더라도 5를 나누면 1이 나와야 하지만 0이 나온다. 왜냐하면 6^100이 int의 범위 값을 넘어가기 때문이다. 이를 해결하기 위해선 2가지 특징을 파악애햐 한다.
- val에 a를 곱할 때 중간중간 m을 나눠준다.
- 계산 범위를 확장한다.
아마 위 2가지 내용을 숙지했다면 어렵지 않게 내용을 변경할 수 있다.
그렇다면 해당 수식을 재귀로 바꿔보면 이런 식이 될 것이다.
using ll = long long; int mod(ll a, ll b, ll m) { if(b==1) return a%m; return a * mod(a,b-1,m) % m; }
아마 반례가 있을 수도 있지만 재귀를 공부한 토대로 내용을 구성해 본다면 위와 같이 작성될 것이다.
귀납적 사고로 문제를 해석해 보자면
1. b = 1이라면 a를 m으로 나눈 나머지를 구한다.
2. b = k라면 이전 b가 k -1의 결과와 a를 곱한 뒤 m을 나눈 값을 구한다.
// b가 k-1의 결과 : a^k-1 % m
- 함수 정의 : a^b 을 m으로 나눈 값을 반환하므로 a,b,m이 인자로 필요하다. (= func(ll a, ll b, ll m))
- base condition : b가 1이면 a^1과 동일하므로 a를 m으로 나눈 나머지를 반환한다.
- 재귀 식 : 현재 a값과 이전 결괏값을 곱한 뒤 m으로 나눈 값을 반환한다.
참고로 이 문제는 반복문을 재귀로 바꾼 것 이므로 시간복잡도O(b)를 가지지만 해당 문제의 시간복잡도를 O(logb)로 줄일 수 있으므로 이 부분은 나중에 문제를 통해 다루도록 한다.
4. 마무리
재귀 정말 어려웠다. 이게 쉬우면서도 조금 수식이 들어거나 절차지향적으로 함수를 파고파고 들어간다면 정말 끝도 없어서 어려웠었는데 이번 단원에 정리를 하면서 조금이나마 감을 잡은듯하다.
재귀 관련 문제를 풀어보며 모든 자료구조와 알고리즘을 정리하게 된다면 게임에서 재귀는 어디에 쓰이는 게 좋을지도 생각해 봐야겠다.
Reference
[실전 알고리즘] 0x0B강 재귀 - BaaaaaaaarkingDog
