이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
https://github.com/AeroCodeX/
재귀 알고리즘(Iterative)의 개념 |
하나의 큰 문제를 똑같은 형태를 갖는 여러개의 부분문제로 나누어 푸는 것.
sum(n) // 1부터 n까지의 합.
sum(10) = 10 + sum(9);
sum(9) = 9 + sum(8);
...
sum(n) = n + sum(n-1);
또 다른 자신이 구했던 이전 값을 활용하여 정답을 계산하며,
비순차적으로 계산이 이루어지는 방식.
여기서 순차적이란 용어는 처음부터 정답까지 모든 경우를 차례대로 계산한다는 의미로 사용되었다.
N=10인 경우의 정답을 구하기 위해 N=0, .. ,9인 경우의 정답까지 전부 구해놓는다는 의미이다.
N=10와 전혀 상관없는 케이스의 정답도 구해놓는다.
비순차적이란 용어는 N=10을 계산하기 위해 필요한 케이스만 계산한다는 의미로 사용되었다.
N=10인 경우의 정답을 구했어도 N=0, .., 9의 경우의 정답이 구해지지 않았을 수 있다.
순회 알고리즘(Iterative)와의 비교 |
- 순회는 이전값도 자신이 계산했다.
- 순회는 순차적으로 계산된다.
순회는 N=10을 계산하는데 N=8이 필요하지 않더라도 구해놓는다.
재귀 알고리즘의 성능 |
재귀로 구현된 알고리즘은 순회에 비해 쉽고 직관적이지만
다음의 이슈로 인한 성능저하를 감수해야 한다.
기본적으로 함수호출이므로, 호출 스택을 잡아먹는다.
불필요한 중복계산이 발생할 수 있다.
5번째 피보나치 숫자를 구하기 위해,
수많은 피보나치 함수가 호출되었고, 특히 1번째 피보나치 숫자는 8번이나 호출되었다.
예제 # N번째 피보나치 수 |
재귀
예제 # N의 약수의 개수 구하기 |
순회
재귀
