[JavaScript] 재귀(Recursive)와 스택(Call Stack)+반복문과 성능 비교

🥕 재귀와 스택

재귀: 주어진 문제를 해결하기 위해 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식이다
. 어떤 루틴이나 프러시저가 자기 자신을 반복적으로 호출하여 문제를 풀어나가는 알고리즘이다.

함수를 정의할 때, 자기 자신을 다시 참조해 호출하는 알고리즘을 말한다.

예를 들어, 팩토리얼 함수를 재귀 함수로 구현할 수 있다.

// 
function factorial(num) {
    if (num === 0) {
        return 1;
    } else {
        return num * factorial(num - 1);
    }
}

console.log(factorial(5)); // Output: 120
}

이 예제에서 factorial 함수는 자기 자신을 호출하여 팩토리얼을 계산한다. 호출 스택에는 각 호출의 상태가 저장되는데, 이때 호출된 함수는 나중에 반환될 값이 저장된 후 스택에서 제거된다.

🥕 스택 (Call Stack)

함수 호출의 실행 컨텍스트를 추적하는 데이터 구조이다.

자바스크립트는 함수 호출을 관리하기 위해 호출 스택(call stack)을 사용한다. 함수가 호출되면 해당 함수의 상태는 스택의 맨 위에 추가되고, 함수가 반환되면 해당 상태는 스택에서 제거된다. 이러한 프로세스는 재귀 함수 호출에도 적용된다.

예를 들어, factorial(5)를 호출하면 다음과 같은 스택이 형성된다.

factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
factorial(0)

스택이 최대 깊이에 도달하면 Maximum call stack size exceeded와 같은 에러가 발생할 수 있으므로 주의해야 한다.

=>재귀 함수를 사용할 때는 호출 스택을 고려하여 스택 오버플로우 에러가 발생하지 않도록 주의해야 한다.

🥕 반복문 VS 재귀 함수

	반복문	재귀 함수
정의	명령을 반복적으로 실행	함수를 다시 호출하여 반복작업 수행
스택 메모리	스택 메모리를 사용하지 않음	함수 호출 시 함수의 매개변수, 지역변수, 리턴값,
		함수 종료 후 돌아가는 위치가 스택메모리에 저장
무한 반복시	무한 루프는 CPU 사이클을 반복적으로 사용	무한 재귀는 스택 오버플로우 발생
속도	빠른 실행	느린 실행

🥕 재귀 함수를 쓰는 이유

1. 변수 사용을 줄일 수 있다.

-> 변수 사용이 줄어든다는 뜻은 프로그램에 오류가 생길 가능성이 줄어들고, 프로그램이 정상적으로 돌아가는지에 대한 증명이 쉬워진다는 뜻이다.

2. 알고리즘 자체가 재귀적인 표현이 자연스러운 경우 (+ 가독성)

-> 재귀 함수의 경우 더욱 직관적임