Recursion | Iteration :: 재귀와 반복

재귀 : Recursion

자기자신을 직간접적으 호출하는 함수 호출

 

큰 문제를 작게 나누어 사용하기 위해 사용함. 

사용방법

재귀를 멈추는 조건이 필요하다. 이미 알고 있는 정보(base case)에 도달한다면 재귀를 멈추어야 한다. 만약 아직 도달하지 못했다면 다시 호출한다. 

call stack

지역변수와 매개변수는 새로 자기 자신을 호출할 때마다 전달되고 함수의 상태는 stack memory에 저장된다. 따라서 모든 재귀는 stack에 일정한 메모리를 소모하고, 만약 재귀가 stack에 할당된 메모리를 소모할 만큼 많이 불린다면 stack overflow error가 발생한다.

반복 : Iteration

for과 while을 사용하여 일련의 명령어 세트를 반복하는 루프

 

stack memory를 소모하지 않고 함수 호출의 voerhead가 없으므로 재귀보다 더 빠르고 (메모리)공간을 효율적이다. 

parameter 등 데이터를 전달할 수 없다.

예상질문

재귀와 반복 중 무엇이 더 빠를까? 이유와 함께 답변하시오

반복이 재귀보다 더 빠르다. 두 방식 모두 연속적으로 명령어를 반복하는 행위지만, 재귀는 함수 호출을 사용하고 반복은 조건부 루프를 사용하여 반복적으로 statement를 실행하기 때문이다. 재귀는 기본적으로 자기자신을 호출함으로서 구현되는데, 이 때 call stack에 호출하는 함수의 지역변수, 매개변수와 반환 주소 등을 모두 담고 있는 stack frame을 저장하고 또 함수를 호출한다. 이러한 과정을 거치기 때문에 실행 중 cpu 사이클을 계속 사용하는 반복보다 더 느릴 수밖에 없다.

---

Reference

Difference Between Recursion and Iteration

Iteration Vs Recursion

Explain the role of a stack in recursive function calls.

스택 프레임