재귀함수

함수가 자신을 다시 호출하는 구조로 만들어진 함수이다.
재귀함수는 종료조건이 있어야 하며, 종료조건을 설정해주지 않으면 무한 반복을 하게된다.
재귀함수로 작성이 되는 코드는 반복문으로도 작성할 수 있다.

1부터 100의 합 구하기
반복문

let s = 0;
for (var i = 1; i < 101; i++) {
	s += i
};
console.log(s); // 5050

let n = 100;
console.log((n*(n+1)/2)); //5050
재귀함수
function f(n) {
    if (n <= 1) {
       return 1 // 종료 조건
    }
    return n + f(n-1) // 재귀함수
}
console.log(f(100)) //5050
// 재귀함수
// 순번   f(n)   n      return       최종
// 1   f(100)  100  100 + f(99)  100+99+98+97+96+95+94..+2+1   
// 2   f(99)   99   99 + f(98)   99+98+97+96+95+94..+2+1 
// 3   f(98)   98   98 + f(97)   98+97+96+95+94..+2+1 
// 4   f(97)   97   97 + f(96)   97+96+95+94..+2+1 
// ...
// 2   f(2)    2    2 + f(1)    2+1
// 1  f(1)    1    1 // return값이 자기 자신을 호출하지 않는 상황

여기서 사용된 for문 조건은 1부터 순회한다.
재귀함수의 경우는 100부터 순회한 다음 호출 스택에 쌓여 있는 값을 처리해 나가게 되는데 스택은 LIFO방식이기 때문에 이때 스택에 제일 마지막으로 반환된 1부터 100까지 순차적으로 더해서 값을 반환하게 된다. 곱하기 방식도 위와 같다.

출처