재귀법
재귀법이란? 함수를 정의할 때 자기 자신을 호출하는 다시 호출하는 방식을 재귀법이라고 한다 다음 예시는 MDN 사이트에 있는 예시이다
1
2
3
4
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에 남아 있어야하기 때문에 메모리를 많이 사용한다
