Recursion

재귀(Recursion)

프로그래밍에서 재귀란 자신을 정의할 때 자기 자신을 재참조하는 것을 말한다.

따라서 재귀 함수란 함수가 호출되어 실행할 때, 함수 내부에서 자기 자신을 다시 호출하는 재귀 호출의 형태를 말한다.

 

스택(Stack)

재귀 호출을 이해하기 위해서는 스택이라는 자료 구조를 먼저 살펴보는 것이 좋다.

왜냐면 우리의 컴퓨터는 호출 스택이라고 불리는 스택을 사용하여 함수를 실행하기 때문이다.

호출 스택은 일반적인 프로그래밍에서도 중요하지만 재귀를 사용할 때 더욱 중요하다.

 

매일 해야 할 일을 포스트잇에 한 장에 하나씩 적는다고 생각해보자. 그리고 포스트잇은 한 곳에 겹쳐 붙여야 한다.

가장 위에 붙어있는 포스트잇에 적혀있는 일부터 해결할 수 있다.

즉, 가장 밑에 있는 일을 하기 위해서는 그 위에 붙어있는 모든 포스트잇을 해결해야만 한다.

 

push 👉	...	👉 pop
	할 일 3
	할 일 2
	할 일 1 (FILO, Fisrt In Last Out)

자료를 넣는 것은 push, 빼는 것은 pop이라고 한다.

 

재귀 함수는 자기 자신을 계속하여 호출하기 때문에 호출 스택에 계속 쌓이게 된다.

이를 방치하면 정해진 메모리 용량을 초과하여 "Maximum call stack size exceeded" 오류가 발생한다.

 

따라서 오류를 방지하기 위해 재귀 호출을 중단시키는 조건 문장이 있어야 하는데,

이것을 Base case 또는 Termination case라고 한다.

 

function factorial (n) {
	if (n === 1) { // Base case, Termination case

	  return 1;
	}
    
	return n * factorial(n - 1);
}

factorial(3); // 6


출처: https://im-developer.tistory.com/102 [Code Playground]

 

재귀 함수 단점

호출 스택에 쌓이게 되므로 값을 반환하기 전까지 메모리 용량을 차지하게 된다.

 

따라서 메모리 효율이 떨어지므로 이러한 경우에는 반복문을 사용하는 것이 성능면에서 더 좋으므로,

상황에 맞게 적절한 방법을 선택하여 사용해야 한다.

 

출처

https://im-developer.tistory.com/102

[JS/Recursion] 자바스크립트, 재귀함수에 대하여 (Recursion)