2주차-recursion (재귀함수)

수강일시 : 2020.09~ 2020.12

출처:  고려대학교 정연돈 교수님 자료구조 강의

 

재귀함수 (recursion)이란 자기 자신을 호출하는 함수이다. 새로운 재귀함수를 만들었을 때, 그 함수가 실행 과정에서 자기 자신을 다시 불러서 동일한 함수가 실행되도록 만든 것을 말한다.

 

Factorial을 재귀함수를 이용하여 구현했을때 호출을 보면 다음과 같이 작동한다.

자기자신을 부른 시점에서 자신의 복사본이 실행되는것으로 볼 수 있다.

 

재귀함수에서 중요한것은 위에서 언급한 바와 같이 자신의 복사본이 실행되기 때문에 stack영역에 함수가 쌓이게 된다. 재귀함수가 호출될 때 마다 stack 영역에 쌓이기 때문에 호출이 계속된다면 stack이 꽉차게되고 stack overflow가 발생 할 수 있다. 따라서 stack overflow 가 발생하지 않도록 재귀함수를 작성할때는 정교하게 고려해야 한다.

예시1

GCD

예시2

전위연산 -> 후위연산