1.6 재귀 함수
재귀 함수는 직간접으로 자기 자신을 호출하는 함수입니다. 재귀 함수는 다음과 같이 두 부분으로 구성됩니다.
• 종료 조건(termination condition) 재귀 함수는 항상 하나 이상의 종료 조건이 있습니다. 함수에서 간단한 경우를 처리하고 자기 자신을 호출하지 않는 조건입니다.
• 본문(body) 재귀 함수의 주요 로직은 본문에 있습니다. 이 본문에는 자기 자신을 호출하는 재귀 확장 구문도 있습니다.
재귀 알고리즘의 중요한 특성 세 가지는 다음과 같습니다.
1. 재귀 알고리즘은 종료 조건이 있어야 합니다.
2. 재귀 알고리즘은 종료 조건에 도달하게 상태를 변경해야 합니다.
3. 재귀 알고리즘은 자기 자신을 호출해야 합니다.
재귀 프로그램의 속도는 스택 오버헤드 때문에 더 느립니다. 루프를 사용한 반복 해결책을 사용해 같은 작업을 수행할 수 있다면 스택 오버헤드를 피하고자 재귀 해결책 대신에 반복 해결책을 사용하는 것이 낫습니다.
Note ≡
종료 조건이 없는 재귀 함수는 계속 실행되다가 결국 스택 메모리를 전부 사용하게 됩니다.