TIL_재귀함수

Today 공부

• [자료구조/알고리즘] 재귀

• 재귀적으로 사고하는 법

  • 잘게 쪼개어 사고하는 법
  • 재귀적 사고
  • 함수 자신의 재귀적 호출
  • 탈출 조건

---

재귀란 ?

• 함수를 스스로 호출하는것
• Programming Concept
• 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법을 재귀(recursion)
• 반복할 구문을 함수단위로 분리해 특정조건이 만족할때까지
  실행하는 패턴

장점 : 알고리즘이 재귀로 표현하기에 자연스러울 경우, 프로그램의 가독성이 좋다
단점 : 값이 리턴되기 전 까지 호출마다 call stack을 새로 생성하므로. 메모리를 많이 사용한다

재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)
재귀의 기초(base case)을 구성합니다.
무한반복을 방지하기 위해서 [반드시] 탈출 조건이 있어야 한다.

---

문제. 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 arrSum 을 작성하세요

for

function arrSum(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

재귀

function arrSum(arr) {
  if (arr.length === 0) { // 1. arr이 빈 배열인 경우 = 0
    return 0;
  }
  // const [head, ...tail] = arr; ---> 구조분해할당 방식  
  const head = arr[0];
  const tail = arr.slice(1); // * arr2는 arr의 첫 요소를 제외한 나머지 배열
  return head + arrSum(tail); // * 2. 그 외의 경우 = arr[0] + arrSum(arr2)
}

base Case

function factorial(n){
// Base Case 무한방복을 방지하기 위한 탈출 조건
// n이 0이면 재귀를 더이상 진행하지 않는다
if(n===0){
return 1;
}
return n* factorial(n-1);
}

---

마치며,

구조분해할당 방식으로 문제를 풀어가는 방법이 있다는걸 보고 깜짝 놀랐다.
오늘 처음으로 접한 개념이라 아직까지는 확실하게 이해하지는 못한거 같다.