[재귀함수] 1-100 합계 구하기

재귀함수 쓰는 이유

변수 사용의 제한

사이드 이펙트가 발생할 확률을 없애준다.

+ 알고리즘을 그대로 연동하는 것이 가능하다.

원칙

명확한 탈출 조건이 있어야 한다. 안그러면, 메모리 오류됨.

코드

const factorial = (num) => {
  if (num <= 1) return num; // 재귀함수 탈출 조건
  else return num + factorial(num-1); // 재귀호출 js 환경에서는 10만개까지 된다고 한다.
}

console.log(factorial(100)) // codepen 환경에서는 9207 개까지 가능했다.

 

풀어지는 원리 (Stack - LIFO 자료구조)

위와 같을 때, else를 타고 스택이 쌓이게 된다.

Stack 은 아래와 같이 쌓인다. (Last In First Out - 1이 가장 늦게 들어오지만 가장 먼저 계산된다.)

factorial(1)

...

factorial(100)

실행은 역순으로 되는데, factorial(1)의 실행 값은 return num. 즉 1이 된다. 

factorial(2) 는 else 문을 타고, 2+factorial(1) -> 2+1 이 된다.

계속되면,

100+ ... + 1 = 5050 이 되는 것.

 

참고

https://velog.io/@tilsong/%EC%9E%AC%EA%B7%80-%ED%95%A8%EC%88%98%EB%8A%94-%EC%96%B8%EC%A0%9C-%EC%8D%A8%EC%95%BC-%ED%95%A0%EA%B9%8C

재귀 함수는 언제 써야 할까?

https://devuna.tistory.com/22

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시