재귀 함수 / 콜스택

JavaScript 알고리즘 & 자료구조 마스터클래스

 

재귀 함수 : 자기 자신을 호출하는 함수

function a(){
  a()
}

 

 

자기 자신을 계속 호출하기 때문에 무한 루프를 돌지 않도록 종료 조건 (base case)가 있어야 한다.

JS의 내장 함수 중 하나인 JSON.parse / JSON.stringify도 재귀적으로 작동한다고 한다.

 

JS에서는 함수의 호출을 관리하는 call stack이라는 자료 구조가 있다. 

함수를 호출하면 스택에 push 된다. 함수가 리턴(또는 종료)되면 pop 된다

 

재귀 함수는 계속해서 자기 자신을 호출하면서 콜 스택에 함수를 추가한다 → 언젠가는 멈춰야 한다

멈추기 위해 필요한 두 가지가 있다.

1. 종료 조건 = base case
2. 매번 다른 인풋으로 자기 자신을 호출한다

 

예를 들어 팩토리얼을 구하는 함수를 아래와 같이 작성할 수 있다.

function factorial(num){
	if(num === 1) return 1 // base case
	return num * factorial(num-1)
}

base case를 제대로 작성하고, 리턴을 제대로 해서 콜 스택에 계속 쌓이지 않도록 주의해야 한다.

그렇지 않으면 스택에 함수가 계속 쌓여 스택 오버플로우가 발생한다.

 

recursion helper method

자신을 직접 부르는 대신, 재귀할 다른 헬퍼 함수를 정의해 사용할 수도 있다.

예를 들어 함수를 호출할 때마다 리셋되지 않는 쌓아갈 변수를 밖에 선언하기 위해 사용할 수 있다.

피보나치 수열을 구하는 함수를 아래와 같이 작성해 보았다.

fib(4) // 3
fib(10) // 55
fib(28) // 317811
fib(35) // 9227465

function fib(n){
  const arr = [1, 1]
  
  const sumFib = (num)=>{
    if(num === n) return
    arr.push(arr[num - 2] + arr[num - 1])
    sumFib(num + 1)
  }
  
  sumFib(2)
  
  return arr[arr.length - 1]
  
}