재귀 알고리즘을 사용하는 3가지 단계
어떻게 풀 것인지 접근방법을 생각해보자
알고리즘 공부를 시작했다. 언제 재귀 알고리즘을 써야하는지, 어떻게 접근해야하는지 나름대로 접근법을 만들었고, 이를 공유해보고자 한다. 나만의 접근법을 만든 이유는, 재귀함수를 구현할 때 너무 많은 고민을 하느라 시작을 못한다는 치명적인 문제점을 해결하기 위함이다. 시간 안에 문제를 풀려면 실마리를 빠르게 찾는 게 중요하기 때문에, 고민 끝에 나름대로 접근 순서를 매뉴얼화해서 낭비되는 시간을 없앴다.
생각의 3단계
1. 반복되는 작업을 찾는다. (recursive step)
반복되는 부분이 있다면 재귀함수나 반복문 중에서 선택할 수 있다.
2. 반복되는 작업을 함수로 생각하고, input 과 output 의 형식을 각각 결정한다. output은 없을 수도 있다. 하지만 만약 output 이 있다면 다음번 input 으로 사용될 것이며, 그럴 때는 타입이 같아야 한다.
3. input 은 한단계씩 점진적으로 변한다. 대부분, 크기나 길이가 한단계씩 줄어든다. 마지막으로 더이상 줄어들 수 없게 된 input 은 종료조건 (base case) 으로 사용된다.
간단한 문제로 예를 들어보자.
문제 : 패러미터로 받은 숫자 n 을 한자리씩, 한칸씩의 공백을 두고 출력하라.
예) input = 12345 / 출력결과 : 1 2 3 4 5
반복되는 작업은 숫자를 한자리씩, 한칸의 공백을 두고 출력하는 것이다. 재귀함수의 리턴값을 사용할 일은 없으므로 output 은 불필요하다. input 이 계속 같다면 재귀함수는 무한으로 호출될 것이므로 점진적으로 값이나 형태를 줄여주어야 한다. 이 문제의 경우에는 input 은 최초의 n에서부터 자릿수를 하나씩 줄여주면 된다. 숫자의 가장 앞자리를 출력한 후 제거하고, 다시 재귀함수의 패러미터로 전달한다.
https://gist.github.com/yeonwooz/fb7a421e88b918d159825c2eafdc0c54
재귀함수 중 가장 유명한 예제인 피보나치 문제를 풀어보자.
문제 : 피보나치 수열의 0번째 항은 0, 1번째 항은 1일 때, 패러미터로 받은 n번째 피보나치 항을 리턴하라. (피보나치 수열의 n 번째 항의 값은 바로 앞의 두 항을 합한 값이다)
예) input = 6 / output = 8
반복되는 작업은 n번째 항의 바로 앞 두항을 더해서 리턴하는 것이다. 이는 output 이면서 동시에 다음번 input 이 된다. input 이 되는 항번호는 계속 줄어들다가, n이 2인 recursive step 에서 0항과 1항을 호출하면서 재귀호출이 종료된다.
https://gist.github.com/yeonwooz/7f53d8c5c8e16e37f6d487362e3e92de
재귀함수의 결과는 스택구조로 저장된다.
유념해야 할 것이, 함수는 호출이후 종료될때까지 메모리에 데이터 스택을 쌓는다는 것이다.
( 참고: http://www.tcpschool.com/c/c_memory_stackframe )
재귀함수는 함수 호출이 종료되기 이전에 다시 같은 함수를 호출하므로, 종료조건에 도달하기 전까지 결과가 스택에서 제거되지 못하고 차례로 쌓인다.
우리는 흔히 함수를 읽을 때 위에서부터 아래까지 쭉 훑어 내려가는 방식에 익숙하지만, 재귀함수를 읽을 때에는 recursive step 에서 재귀호출이 이루어지는 라인이 종료조건에 도달하는 순간까지 그 다음라인은 실행되지 않는다는 것을 명심해야 한다. 이 시점이 바로 스택에 데이터가 쌓이는 시점이다. 종료조건에 도달하고 나면 비로소 호출되었던 함수들이 역순으로 종료되면서 쌓였던 스택의 데이터가 하나씩 pop 되어 나온다.
또한 당연하게도, 반복문에서 루프를 돌때 블록 안에서 선언한 변수가 매번 초기화되는 것과 마찬가지로 함수 블록 안에서 선언한 변수는 매번 재귀함수가 호출될 때마다 초기화된다.
가령, 십진수를 이진수로 변환해서 출력하는 데에 재귀함수를 이용하는 경우를 생각해보자. 십진수를 이진수로 변환한 값은, 몫이 1이 될때까지 십진수를 2로 반복해서 나누고, 그 과정에서 생겨난 몫과 나머지를 거꾸로 나열해서 구할 수 있다.
10의 이진수는, 몫과 나머지를 거꾸로 나열한 1010 이다 이를 함수로 작성해보면 다음과 같다.
https://gist.github.com/yeonwooz/f9e21cf87a25b12a313554faf57108a8
함수는 13번째 라인에 도달한 후, n / 2 가 1이 될때까지 반복해서 MakeBinaryRecursive 함수를 호출한다.
만약 16번째 라인의 Console 출력을 12번째라인에서 한다면 출력결과는 0110 (위의 그림에서 DCAB 순)이다. 생각해보면 이는 당연한데, 최초의 n이 10이었으니 종료조건에 걸리지 않아서 recursive step 으로 넘어왔고, 10을 2로 나눈 나머지는 0이므로 가장 먼저 0이 출력된다. 그리고 다시 5 가 패러미터로 넘어와서 다음 출력되는 값은 1이다. 그 다음 패러미터인 2는 종료조건에 걸리므로 몫과 나머지를 차례대로 출력하여 1,0을 출력하는 것이다. 이 값들은 함수가 실행되는 동안 메모리 어딘가에 스택구조로 저장된다.
하지만 만약 출력을 재귀호출 이후인 16번째 라인에서 하게되면, 이 16번째 라인의 Console 출력은 재귀호출이 종료조건에 걸릴 때까지 실행되지 않는다. 패러미터가 2가 되어 종료조건에 걸리고 나면, 재귀호출이 발생하는 동안 스택에 쌓여있던 값들이 차례대로 pop 되어 나온다. 16번째 라인에서는 이렇게 pop 되어 나오는 값들을 출력하는 것이므로, 들어간 순서와 반대로 출력되는 것이다.
Photo by Syd Wachs on Unsplash
