Recursive Functions

Recursive Functions란?

• 재귀함수. 원래의 자리로 되돌아가거다 되돌아온다.
  자기 자신을 부르는 함수.

특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.
우리가 흔히 알고있는 반복문은 for, while등이 있는데,
이러한 반복문으로 구현 가능한 로직은 모두 재귀함수로도 가능하고 그 반대 역시 가능하다.

재귀 함수의 가장 대표적인 사용 예제는 팩토리얼이다.

int factorial (int n) {
	if(n === 1) {
    	return 1;
   }
   
   return n * factorial(n - 1);

}

stack overflow

재귀함수 사용시 스택 오버 플로우를 주의해야한다.

int factorial (int n) {
 return n * factorial(n - 1)
 
}

여기서 n === 1일때 리턴하라는 값을 주지 않고, -1, -2, -3 ... -n까지 무한대로 실항되게 될것이다. 사실상 컴퓨터의 메모리에는 한계가 있으니 무한대는 불가능하고 스택 오버플로우 문제가 발생하게 된다.

재귀함수의 장단점

장점

• 변수 여럿을 만들 필요가 없다.
• while문이나 for문같은 반복문을 사용하지 않아도 되기에 코드가 간결해진다

단점

• 지속적으로 함수를 호출하게 되면서 지역 변수, 매개 변수, 반환값을 모두 process stack에 저장해야한다. 이런 과정은 선언한 변수의 값만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게 되고, 이는 속도 저하로 이어진다.

• 함수 호출 -> 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 된다.

출처