[WEEK02] 재귀함수

[Do it 자료구조와 함께 배우는 알고리즘 입문 with 파이썬] + [이것이 취업을 위한 코딩테스트다]  개념정리

 

재귀함수 (Recursive Function)

: 어떤 이벤트에서 자기 자신을 포함 -> 다시 자기 자신을 사용하여 정의

: factorial(n)이 factorial(n-1)을 호출함 => 재귀 호출

: 재귀함수의 수행은 스택 자료구조와 동일함

    (함수를 계속해서 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 끝남)

     => 따라서 재귀적으로 함수를 표현할 때는 반드시 if 문을 이용하여 종료조건을 구현해야함

: 재귀 함수를 활용하여 소스코드를 작성하는 것은 수학의 점화식과 유사함

 

직접재귀와 간접 재귀

직접재귀 : 자기 자신과 똑같은 함수 호출

간접재귀 : 다른 함수를 통해 자기자신과 똑같은 함수 호출

 

재귀 알고리즘의 2가지 분석방법 (Do it 참고)

1) 하향식

2) 상향식

 

재귀 알고리즘의 비재귀적 표현 (Do it 참고)

1) 꼬리재귀제거

2) 재귀를 제거