재귀함수

재귀란?

함수를 스스로 호출하는 것을 말한다.

function foo() {
  foo();
}

재귀를 언제 사용해야 될까 ?

모든 재귀는 반복문으로 해결이 가능하다.
하지만 10번 100번이고 반복문을 사용한다면 하드코딩이 되기 때문에
재귀함수로 간결하게 정리해주는것이 편하다

재귀는 이런 상황에서 사용하기 가장 적합하다!

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

재귀함수 코드구현 예시

function arrSum(arr) {
//Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
if (arr의 길이가 0인 경우) {
return 0;
}
/*

• Recursive Case : 그렇지 않은 경우
• 문제를 더 이상 쪼갤 수 없는 경우
• head: 배열의 첫 요소
• tail: 배열의 첫 요소만 제거된 배열
  */
  return head + arrSum(tail);
  }

중요포인트 ! 재귀함수는 무한반복을 방지하기 위해 탈출조건이 있어야 한다.

재귀의 장점, 단점

장점 - 알고리즘이 재귀로 표현하기에 자연스러울 경우, 프로그램의 가독성이 좋다
단점 - 기본적으로 스택 메모리를 사용하는데 재귀의 깊이가 깊어졌을 때, stack overflow가 발생하면서 프로그램이 비정상적으로 종료 될 수 있다