#2. 재귀

<재귀 알고리즘>

- 재귀적(recursive) : 알고리즘 자신을 사용하여 정의된 알고리즘

- 비재귀적(nonrecursive) : 재귀적의 반대

 

 

<재귀의 요소>

- 재귀 케이스(recursion) : 다음 재귀호출을 하는 부분으로 작아진 subproblem을 대상으로 작성

- 베이스 케이스(base case) : 종료조건. subproblem이 충분히 작아지면 직접 해결

 

 

n부터 1까지 합을 구하는 Sum 함수의 의사코드를 예시로 보면,

 

n = 3일 때 작동원리를 살펴보면,

 

 

<기본 규칙>

- 베이스 케이스 : 재귀함수에서 항상 가져야 하는 부분으로 이 부분은 재귀 없이 직접 해결

- 진행 방향 : 재귀호출은 항상 베이스 케이스를 향하는 방향으로 진행

- 정상작동 가정 : 모든 재귀호출이 정상 작동한다고 가정

- 적절한 사용 : 성능저하 때문에 꼭 필요할 때만 사용(피보나치 수열 표현하면 함수 호출 너무 많이 반복)