JavaScript 재귀함수

CodeLog·2020년 11월 24일

CallStack JavaScript base case recursion 재귀함수 탈출조건

재귀함수란?

사전적 의미

재귀 再歸
명사 : 원래의 자리로 되돌아가거나 되돌아옴.

recursion
명사 : 수학 반복, 되풀이

javascript에서 재귀함수는 자기자신을 호출 한다 입니다!

문법상 형태

factorial을 재귀적으로 만든 형태입니다.
(4! 은 1 x 2 x 3 x 4 = 24입니다)
친해지기 힘든 모습을 하고 있네요..
return의 형태가 자신의 함수이름을 띄고있습니다
결론적으로 return을 하는데 자기를 계속 호출하면서 함수내부 로직을 반복적으로 작동시키게 됩니다.

function factorial(number){
  if(number === 1){
    return 1;
  }
  return number * factorial( number -1 );
}
factorial(4);
//결과 24

위 코드를 하나씩 풀어보자면

4 x factorial(3)
3 x factorial(2)
2 x factorial(1)
1
최초 4의 number값을 가지고 재귀를 하게되면 위와같은 순서를 따릅니다.

재귀함수에서 중요한 포인트!

1. 탈출조건

재귀는 탈출조건이 없다면 계속 자신을 호출하다가 call stack error를 만나게 될겁니다.
메모리는 한정적인데 계속 호출해서 사용했다는 이야기가 되겠네요.
따라서 탈출조건은 아주 중요합니다
factorial을 구하는 재귀 함수에서 탈출조건을 if문으로 명시하고 있습니다.
재귀를 호출할때 number - 1 연산에서 점진적으로 number값을 줄여나가 탈출조건 if문을 만나면
더이상 재귀를 하지 않게 됩니다.

function factorial(number){
  //탈출조건
  if(number < 0){
    return;
  }
  //base case
  if(number === 0){
	return 1;
  }
  
  //recursion
  return number * factorial( number -1 );
}
factorial(4);
//결과 24

2. base case

탈출조건과 base case는 어떻게보면 같은 기능을 한다고 생각 할 수 있지만, 차이가 조금 있습니다. 탈출은 잘못된 값 또는 재귀를 멈춰야하는 필요한 상황에 대응하기 위함이고, base case는 원하는 결과물을 얻기위해 마지막 연산의 조건이라 생각하면 될것 같습니다.
factorial(4)의 경우 4 x 3 x 2 x 1 순서라면 number가 0일때 1을 리턴하여 재귀를 멈추고 리턴 되는 값을 연산하게 됩니다.

성능면에서의 재귀함수

반복문으로도 재귀처럼 만들 수 있을것입니다.
하지만 복잡해질 수 있고 코드가 가독성이 떨어 질 수 있습니다.
그런 부분을 재귀함수로 전환한다면 직관적으로 알아보기 쉬울 수 있습니다.
그럼 왜 재귀를 쓸까요?
한가지 예로 배열의 중첩을 생각해 볼수 있습니다.
1차원 배열이아니라 10차원 이상이라면 재귀로 풀어내는게 코드가 간결할 수 있고 쉽게 짤 수있습니다.
그러나 재귀는 호출 될 때마다 call Stack에 쌓이게 됩니다. 즉, 성능 저하를 일으킬 수 있기때문에 필요한곳에 적절하게 사용해야 합니다.