재귀함수란?

재귀함수란 함수 내부에서 자기 자신을 호출하는 함수를 의미한다.
반복문을 돌리듯이 자기 자신을 끊임없이 호출하다가 특정 조건이 되면 빠져나오는 함수이다.

1부터 n까지의 정수를 곱하는 팩토리얼 함수를 재귀를 이용하여 구현해보면 다음과 같다.

function factorial(num){
  if(num === 0) return 1;

  return num * factorial(num - 1);
}

factorial(4);

위의 함수를 실행시키면 콜스택에는 아래와 같이 함수가 쌓이게된다.

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

num이 0이 되었을 때 1을 리턴하며 밑에 쌓인 함수들을 다시 실행 시킨다.

factorial(0); -> 1
factorial(1); -> 1
factorial(2); -> 2
factorial(3); -> 6
factorial(4); -> 24

문자열 뒤집기

function reverse(str){
  if(str.length === 1) return str;
  
  return reverse(str.slice(1)) + str[0];
}

reverse('awesome')

위의 함수를 실행시키면 콜스택에는 아래와 같이 함수가 쌓이게된다.

reverse('e') 
reverse('me') 
reverse('ome') 
reverse('some') 
reverse('esome') 
reverse('wesome') 
reverse('awesome') 

str의 길이가 1이 되었을때 e를 리턴하며 밑에 쌓인 함수들을 차례로 실행시킨다.

reverse('e') -> 'e'
reverse('me') -> 'em'
reverse('ome') -> 'emo'
reverse('some') -> 'emos'
reverse('esome') -> 'emose'
reverse('wesome') -> 'emosew'
reverse('awesome') -> -> 'emosewa'

재귀함수는 성능이 반복문에 비해 좋지 않다.
함수를 반복적으로 호출하면, 스택에 쌓이는 메모리가 커지고, 호출 횟수가 많아지면 스택오버플로우가 발생할 수 있다.