재귀로 많은 문제를 해결 할 수 있지만, 제대로 사용하지 않으면 O(2^N)같이 느린 효율성을 가진 프로그램이 만들어지는 문제가 있다. 이러한 문제를 해결하는 방법에 대해서 알아보자.
불필요한 재귀 호출
public static int max(ArrayList<Integer> arrayList){ if (arrayList.size() == 1) return arrayList.get(0); //1 if (arrayList.get(0) > max(new ArrayList<>(arrayList.subList(1,arrayList.size())))) return arrayList.get(0); //2 else return max(new ArrayList<>(arrayList.subList(1,arrayList.size()))); }다음과 같은 코드가 있다. 이 코드는 불필요한 재귀 일어나는 코드이다. 일반적으로 배열에서 가장 큰 값을 찾을 때 배열의 길이 N만큼의 단계가 필요하다. 하지만 이 코드를 보자
1에서 비교를 위해 재귀를 실행한다. 이 후에 아닐 경우에도2에서 재귀를 실행하게 된다. 이러한 경우 기존 루프문을 도는 것 보다 많은 단계를 필요로 한다. 만약 배열이[2,3,4]라면2와 값을 비교하기 위해[3,4]에서 큰 값을[3,4]는 비교를 위해,3 < 4이기 때문에 재귀를 두번 반복하고 값은 값인4를 리턴한다. 이 코드에[1,2,3,4,5]배열을 넣을 경우 약 31번 단계를 필요로 한다.
빅 오를 위한 작은 개선
public static int max2(ArrayList<Integer> arrayList){ if (arrayList.size() == 1) return arrayList.get(0); int maxOfRemainder = max2(new ArrayList<>(arrayList.subList(1,arrayList.size()))); if (arrayList.get(0) > maxOfRemainder) return arrayList.get(0); else return maxOfRemainder; }위 코드를 다음과 같이 변경했다. 이러면 어떠한 일이 발생할까?? 우선 이 코드는 위 코드와 달리 재귀를 N번만 한다.
재귀의 효율성
개선한 max2()는 단 N번만 반본한다. 이는 O(N)이다. 그렇다면 개선되기 전 max()코드의 빅오는 몇 일까?? O(2^N)이다. 이 문제를 통해 우리는 불필요한 재귀가 얼마나 비효율적인 알 수 있었다. O(N) 과 O(2^N) 엄청난 차이가 있다. 따라서 우리는 불필요한 재귀의 호출을 최대한 피해야한다.
하위 문제 중첩
피보나치 수열이 있다고 가정하자. 이 때 N번째 피보차니 수를 반환하는 코드가 있다.
public static int fib(int n){ if(n <= 1) return n; return fib(n - 1) + fib(n - 2); }자신을 두번 호출하는 재귀 함수는 O(2^N)이 되기 쉽다. 피보나치 수열 또 한 O(2^N)이다. 최댓값을 구하는 함수 max()의 경우 최적화를 쉽게 할 수 있었으나, 피보나치 수열의 최적화는 쉽지 않다. 왜냐하면 변수에 저장할 데이터가 단지 하나가 아니기 때문이다. 재귀하는
n-1과n-2를 모두 계산해야하는데 그 중 한 결과만 저장해서는 나머지 한 결과를 얻지 못 한다.
컴퓨터 과학에서는 이를 하위 문제 중첩이라고 한다. 동일한 문제를 작게 만들어 해결함으로써 어떤 문제를 풀 때 더 작은 문제를 하위 문제라 부른다. 이는 새로운 개념이 아니다. 재귀를 논하면서 내내 자주 다뤘던 개념이다. 피보나치 수열 또한 더 작은 수를 먼저 계산해서 각 수를 계산한다. 이렇게 더 작은 수를 계산하는 것이 하위 문제다. 그렇지만 하위 문제가 중첩되는 이유는 결과적으로 같은 함수를 여러 번 중복해서 호출하기 때문이다. 즉 위 코드에서fib(n-1)은fib(n-2)했던 작업을 수차례 똑같이 반복한다. 그렇다면 이 코드의 효율성을 어떻게 올릴 수 있을까???
메모이제이션을 통한 동적 프로그래밍
동적 프로그래밍은 하위 문제가 중첩되는 재귀 문제를 최적화하는 절차다. 동적 프로그래밍을 통한 알고리즘에 최적화에는 일반적으로 두 기법 중 하나를 사용한다.
첫번 째는 메모이제이션이라 불린다. 하위 문제가 중첩될 때 재귀 호출을 감소시키는 간단하면서도 아주 뛰어난 기법이다. 위 피보나치 코드를 통해 메모제이션의 예를 들어보자.
우리는{3:2, 4: 3, 5:, 5, 6: 8}이란 걸 알고있다. 그렇다면 컴퓨터 또한 계산 결과를 해시테이블에 추가하는 식으로 동작하게 되면 어떨까?? 이 방법이 바로 메모제이션이다. 계산한 값을 해시테이블에 추가하고 중첩이 일어날 경우 해시테일블에서 그 값을 바로 읽어 올 수 있다.
하지만 한 가지 문제가 있다. 재귀 함수는 해시 테이블에 어떻게 접근해야 할까??
바로 두 번째 인자로 해시 테이블을 전달하면 된다. 해시테이블은 메모리 내 객체이믈 함수 호출 중에 수정하더라도 한 재귀 호출에서 다음 재귀 호출로 전달 할 수 있다. 심지어 호출 스택을 풀어 갈 때도 마찬가지다. 처음 호출할 때 테이블이 비어 있어도 최초 호출이 실행이 끝나는 시점에는 데이터로 가득 차 있을 것이다.
메모이제이션 구현
public static int fib2(int n, Hashtable<Integer,Integer> ht){ if(n <= 1 ) return n; if (ht.get(n) == null) ht.put(n,fib2(n-1,ht) + fib2(n - 2, ht)); return ht.get(n); }이 코드는 한번 계산된 수면 다시 계산하지 않고, 해시 테이블에서 그 값을 가져온다. 그렇다면 빅 오는 어떻게 표현 할 수 있을까?? 표를 보자.
이 표를 보면 대략 2N-1 단계를 거친다. 즉 O(N)번이다. 기존 O(2^N)가 엄청난 차이를 자랑한다.
상향식을 통한 동적 프로그래밍
이제 두번 째 방법을 알아보자. 바로 상향식이라 불리는 두 번째 기법은 훨씬 세덜 세련되고 심지어 기법이라고 부르기도 애매하다. 상향식은 그저 같은 문제를 재귀 대신 다른 방식으로 해결한다는 뜻이다. 상향식이 동적 프로그래밍의 하나로 간주되는 이유는 동적 프로그래밍이 재귀적으로 풀 수 있는 문제에 대해 중첩되는 하위 문제를 중복 호출 하지 않게 해주기 때문이다. 재귀 대신 반복을 사용하는 것도 엄밀히 말해 이렇게 하는 방법 중 하나다.
문제가 재귀로 더 자연스럽게 풀린다면 오히려 상향식이 기법에 가까워진다. 피보나치가 재귀로 깔끔하게 풀리는 예다. 이재 피보나치 함수를 상향식으로 구현해 보자.public static int fib3(int n){ if (n == 0) return 0; int a = 0; int b = 1; int temp; for (int i = 1; i < n; i++){ temp = a; a = b; b = temp + a; } return b; }코드를 분석해보자. 피보나치 수열은 (n-1)+(n-2) = n번째 수열이다. 그렇기에 n번 까지 루프를 반복하면서 계속 이러한 값을 더해주면 피보나치 수열을 구현 할 수 있다. 즉 1~N까지 루프를 도므로 O(N)이다.
메모이제이션 대 상향식
재귀가 주어진 문제를 간결하고 직관적으로 해결 할 수 있으면 재귀로 문제를 해결하는 것이 좋다. 하지만 일반적으로 재귀를 사용 할 경우 많은 메모리가 소모된다. 컴퓨터는 재귀 함수를 사용 할 경우 모든 호출 스택을 기억해야 한다. 또한 하위 문제 중첩을 해결 하기 위해서 해시 함수를 사용한다면 이 또한 추가로 컴퓨터 메모리를 소모한다. 그렇기에 재귀가 매우 직관적이지 않은 이상 일반적으로 상향식을 택하는 편이 오히려 더 좋다. 재귀가 더 직관적이면 메모이제션으로 코드의 효율성을 높여야 한다.
결론
코드는 재귀 함수를 사용 할 경우 매우 낮은 효율성을 가질 수 있다. 그렇기에 이를 해결하기 위해 메모이제이션을 잘 활용해야 한다. 또한 일반적으로 재귀 함수보다 루프(상향식)을 통해 문제를 해결하는 것이 메모리적으로 더욱 좋다.
