글을 읽기전에
자바스크립트에 익숙하다는 것을 가정하고 쓴 글입니다.
제가 공부한 것을 정리한 것이므로 틀린 정보가 있을 수 있습니다.

재귀함수

자기자신을 호출하는 함수입니다.

recursion 이라고 하구요.

뭐......라고 딱히 설명할게 없네요.

음 쓰는 이유는 코드가 깔끔해지고 변수를 여러개 선언하지 않아도 됩니다!

재귀의 규칙

n을 2로 나눠서 1이하가 되려면 몇번 나눠야 되는지 계산해야하는 문제가 있습니다.
반복문을 이용해서 풀면

function solveWithLoop(n: number) {
  let count = 0;
  while (true) {
    if (n <= 1) return count;
    n /= 2;
    count += 1;
  }
}

이렇게 풀 수 있겠지요!

그런데 이 코드를 재귀로 바꾸려면 어떻게 해야할까요?!

먼저 재귀에는 규칙이 있습니다.

기저조건(종료조건)

재귀는 자기자신을 계속 호출하기 때문에 그 과정을 멈출 조건이 필요하다.
이를 기저조건 혹은 종료조건이라고 부른다.

분할 정복 방식

문제를 작은 단위로 나눠서 문제를 해결하는 것을 말한다.
한 문제를 풀기위해 계속 부분문제를 만들어나가는 방식이다.

이제 두가지 규칙을 알았으니 위의 문제에서 기저조건을 찾아보고 분할정복해볼까요?

n을 2로 나눠서 1이하가 되려면 몇번 나눠야 되는지 계산해야하는 문제가 있습니다.

기저조건: n이 1이하가 되었다.

분할정복:n을 2로 나눈 수인 n/2 를 2로 나누는 문제는 위 문제의 부분문제이이다. n/2 를 2로 나눈 수인 n/4를 2로 나누는 문제는 결국 위의 문제의 부분문제가 된다. 기저조건에 도달할 때까지 부분문제를 계속 도출해내면 된다.

찾아낸 기저조건과 생각해낸 분할정복방식으로 코드를 짜면

function solveWithRecursion(n,count){
if(n<=1)
  return count;
  return solveWithRecursion(n/2,count+1)
}

이렇게 쓸수 있겟지요!!

주의할 점

모든 함수는 호출 시에 콜스택에 쌓입니다.
재귀함수도 마찬가지라서
기저조건에 도달할 때까지 메모리에 계속해서 함수호출이 쌓이게 됩니다.
만약 기저조건이 잘못되었다면

js에서 재귀를 사용할 때는 주의해야 하는데
정상적인 재귀여도 메모리초과가 일어날 수 있습니다.

따라서 사실 저는 js로 알고리즘 풀 때는 재귀를 선호하지 않습니다.

사실 꼬리재귀로 해결이 가능할 수도 있습니다.
하지만 코테 도중 정상적인 재귀인데 스택오버플로우가 일어날 경우 ......멘붕이 와서 다음 문제를 못푸는 경우가 생길수도 있어서...........,,.,.,.,..,,.,.,.,.,.,