[알고리즘]04. 재귀 함수

재귀 ( recursive ) 함수

알고리즘을 공부하려면 작성할 수 있어야 한다. 

큰 문제를 반복 적용 가능한 작은 문제로 나워 푸는 방법이다. 즉, 어떤 함수가 매개변수만 바뀌어 자기 스스로를 호출하는 방식으로 구현

재귀가 필요한 알고리즘이 많음

• 이진 검색
• 트리 검색
• 퀵 정렬
• 그래프 알고리즘

재귀 함수의 장단점

장점	단점
가독성이 좋음	재귀적 문제 분석/설계가 안 직관적
코드가 짧음	맹목적인 믿음이 필요
각 단계의 변수 상태가 자동 저장됨 -> 함수의 스택 프레임 덕분	스택 오버플로 발생 가능
코드 검증도 쉬움	함수 호출에 따른 과부하

꼬리 호출

• 기존 재귀 함수를 보완하는 방식
• 함수 코드 제일 마지막에서 다른 함수를 호출하는 경우
• 그 후에 실행하는 명령어가 없음

꼬리 호출과 시택 프레임

• 스택 프레임이 존재하는 이유
  • 함수에서 사용 중인 변수 값을 유지하기 위해
  • 타 함수 호출 후 반환되면 스택에 저장했던 값을 되덜려 사용
• 꼬리 호출의 경우는 타 함수로 부터 반환 후 더 이상 연산이 없음
  • 곧바로 호출자로 반환
• 따라서 스택 프레임에 저장해 놓은 변수 값을 재상용하지 않음
  • 이러한 경우 컴파일러가 스택 프레임을 따로 안 마드는 최적화를 하기로 함
    • 꼬리 호출 제거 ( tail call elimination)
    • 꼬리 호출 최적화 (tail  call optimization)

꼬리 재귀 (tail recursion)

• 꼬리 호출의 특수한 경우
• 마지막 에 호출하는 함수 ( 꼬리 호출) 가 자기 자신 (재귀)
• 꼬리 호출과 똑같은 최적화가 적용됨

꼬리 재귀 함수 작성하기

• 보통 꼬리 재귀 함수가 덜 직관적
• 그러나 이런 식으로 작성된 코드가 종종 보임
• 가장 큰 이유는 앞에서 말했던 최적화

꼬리 호출 최적화를 지원 안 하는 언어라면?

• 안 돼도 충분한 의미가 있음
• 꼬리 재귀는 반복문으로 쉽게 변경 가능