재귀법

재귀법이란? 함수를 정의할 때 자기 자신을 호출하는 다시 호출하는 방식을 재귀법이라고 한다
다음 예시는 MDN 사이트에 있는 예시이다

function factorial(n){
  if ((n == 0) || (n == 1))
    return 1;
  else
    return (n * factorial(n - 1));
}

위 코드에서 보면 else문에서 자기 자신을 다시 호출하는 것을 볼 수 있을 것이다 이렇게 함수 정의시 자기 자신을 호출하는 방식이다
재귀법 계속해서 자기를 호출하는 방식이기 때문에 무한하게 재귀하는 것을 방지하는 위한 탈출 조건이 필요한다

탈출 조건

위 코드에서 탈출조건은 if ((n == 0) || (n == 1)) 이 부분이다 팩토리얼을 구하기위해서

4팩토리얼이라고 가정

• 4 * factorial(3)
• 4*3*factorial(3)
• 4*3*2*factorial(1)
• 4*3*2*1 (여기서 위에 조건식에 걸려서 탈출한다)

재귀 부분

재귀 함수에서 재귀 부분은 단순히 자기 자신만 호출하는 것이 아니라 어떤 문제를 풀어야한다면 그 문제를 작게 분해하는 과정이 들어가야한다 단순히 자기 자신을 호출하는 것은 일반적인 반복문이기 때문이다 위 코드에서는 return (n * factorial(n - 1)); 이 부분이 계속해서 n을 밖으로 빼주면서 팩토리얼의 크기를 줄이고 있다

재귀를 사용하는 이유

• 프로그램을 좀더 단순하게 작성할 수 있다
• 단순하게 작성하기 때문에 가독성또한 좋아진다

단점

• 재귀함수 방식으로 계속해서 호출하게 되면 호출을 한 함수는 호출을 당한 함수가 끝나기 전까지 계속 callstack에 남아 있어야하기 때문에 메모리를 많이 사용한다