동적알고리즘(재귀적 알고리즘)을 구현하는데 있어서

 

1. 해결하고자 하는 알고리즘의 전체를 파악한다.
예를 들어 피보나치 수열을 구하고자 할 때 첫째항과 둘째항은 항상 1이고 n번째 항은 n-1항과 n-2항의 합이라는 성질을 파악해야한다.
2. 성질을 파악한 뒤 일반화된 식을 세워본다.
팩토리얼을 예로 들면 5! = 5*4*3*2*1 이라는 것에서  n! = n*n-1*n-2...*1이라는 것을 유추할 수 있고 깊숙이 파고들면 n! = n * (n-1) != n * (n-1) * (n-2) !라는 성질을 알 수 있다. 머릿속으로 생각 할 수 있어도 한번쯤은 확실히 적어본다.
3. 그 다음 조건문을 이용하여 초기화를 끝낸다.
4. 초기화가 끝났다면 유추해낸 식을 이용하여 전체식을 구성한다.


참고로 재귀호출은 재귀호출을 사용하지 않은 더 자세한 구현보다 효율이 낫다. 이는 알고리즘 측면에서 보면
재귀호출 n^n
이고 구현은 그보다 낫게 나타나기 때문이다.