재귀 함수 는 자기 자신 을 호출 하 는 함수 입니다 . 점화식 과 비슷 한데 , 예시 를 보 면 좀 더 잘 이해 할 수 있 습니다 . 
 fibo ( 1 ) : 1 
 fibo ( 2 ) : 1 
 fibo ( 3 ) : 2 
 fibo ( 4 ) : 3 
 fibo ( 5 ) : 5 
 fibo ( 6 ) : 8 
 이름 에서 눈치챘 을 수 도 있 겠 지만 , 이 함수 는 피보나치 수열 의 a 항 을 구해 주 는 함수 입니다 . a 가 3 미 만 , 즉 1 과 2 이 라면 1 을 반환 하 고 , 그렇 지 않 다면 전 항 과 전 의 전 항 을 반환 합니다 . 그런데 , 이 피보나치 수열 함수 는 조금 느리 게 움직입니다 . 
 잘 보 면 , fibo ( a ) 를 구하 기 위해 호출 하 는 함수 의 갯 수 가 fibo ( a ) 에 비례 해서 커집니다 . fibo ( a ) 는 1 . 618 a 에 비례 해 커지 므로 , 결론 적 으로 fibo ( a ) 를 구하 기 위해 걸리 는 시간 은 1 . 618 a 에 비례 해 커집니다 . 조금 더 개선 할 수 있 을 것 같 습니다 . 
 자 , 이렇게 하 면 배열 에 이미 구해 둔 값 들 을 저장 해 놓 으니까 좀 낫 죠 ? 이미 구한 값 은 바로 바로 꺼내 서 쓸 수 있 고 . 이런 것 을 메모 이제 이 션 이 라 합니다 . 여기 서 는 걸리 는 시간 이 a 에 비례 해서 커지 겠 군요 . 그런데 여기 서 문제 가 생겼 습니다 . 수 가 많 아 지 다 보 니 , arr [ 100 ] 으로 는 모자라 는 경우 가 생겼 습니다 . 200 으로 늘렸 지만 한참 모자랍니다 ( 사실 94 항만 해도 unsigned long long 의 최대 크기 인 264 - 1 을 넘어갑니다 ) . 어떻게 해야 할까요 ? 
 일반 적 으로 같 은 일 을 하 는 재귀 함수 와 반 복문 중 속도 가 더 빠른 것 은 반 복문 입니다 . 함수 호출 에 따른 오버헤드 가 없 기 때문 입니다 . 하지만 컴파일러 는 return 뒤 에 수식 ( 연산자 ) 없 는 값 이 오 면 꼬리 재귀 최적화 라고 불리 는 것 을 해 주 는데 , 이것 을 통해 재귀 함수 는 반 복문 과 동등 한 수준 의 속도 를 얻 게 됩니다 ( 물론 반 복문 쪽 이 약간 더 빠릅니다 ) . 이 코드 는 꼬리 재귀 를 사용 할 뿐 만 아니 라 , a 와 b 두 변수 에 만 전 항 과 전 의 전 항 을 저장 해 메모리 를 아낍니다 . 이런 기법 을 슬 라 이싱 이 라고 합니다 . 하지만 두 번 째 코드 는 fibo ( 10 ) 을 구한 후 추가 적 인 함수 호출 없이 fibo ( 5 ) 를 구할 수 있 었 지만 , 이번 코드 는 얄 짤 없이 처음 부터 계산 해야 합니다 . 장단점 이 있 지요 . 
 특정 작업 들 은 재귀함수 를 사용 하 면 아주 쉽 게 해결 이 가능 한 경우 가 있 습니다 . 하지만 재귀 함수 를 사용 하 는 알고리즘 은 일반 적 으로 느리 고 ( 같 은 부분 을 여러 번 계산 하 기 때문 ) , 또 설령 같 은 알고리즘 으로 동작 한다 해도 함수 호출 에 의한 오버헤드 가 발생 합니다 . 꼬리 재귀 최적화 도 아무 컴파일러 나 해 주 는 것 이 아닙니다 . 반 복문 으로 도 해결 가능 한 작업 이 라면 , 반 복문 을 사용 해 주 세요 . 
 조금 더 머리 를 굴리 면 log a 에 비례 한 시간 만 으로 도 fibo ( a ) 를 구할 수 있 습니다 ( 사실 은 log 2 a 지만 , 밑 변환 을 해 주 면 상수 배 입니다 ) . 또 , C ++ 이 라는 언어 에서 는 a 가 1 이 던 100 이 던 같 은 시간 안 에 fibo ( a ) 를 출력 할 수 있 습니다 ( 물론 여기 서 말 하 는 시간 은 컴파일 하 는 데 걸리 는 시간 을 제외 한 것 입니다 ) . 잘 고민 해 보 세요 !