자료구조/알고리즘) 재귀

재귀

어떤 함수가 자기 자신을 호출하는 것으로
어떤 문제를 더 작은 동일한 구조의 반복으로 생각하여 문제를 해결하는 방법
모든 재귀 함수는 반복문으로 표현할 수 있지만, 대부분 재귀 코드가 간결하고 이해하기 쉽다

재귀의 사용을 고려해봐야 할 때

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• 중첩 반복문이 많거나 중첩 횟수를 예측하기 어려운 경우
  알고리즘 문제에서 많이 사용된다

재귀 함수의 실행

function sum(num) {
  if(num === 0){
    return 0;
  }
  if(num === 1){
    return 1;
  }

  return num + sum(num - 1);
}

num이 0이거나 1이 아닐 경우

num + sum(num - 1)을 반환한다

sum(4)의 경우

return 4 + sum(3);
    return 3 + sum(2);
        return 2 + sum(1); // 
            return 1 // if num===1 일 경우에 해당

가장 마지막 반환 값인 sum(1)의 return 1 부터 계산이 시작된다

return 4 + 6; // 4 + sum(3)의 값
    return 3 + 3; // 3 + sum(2)의 값
        return 2 + 1; // 2 + sum(1)의 값
            return 1;