[C/F TIL] 41일차 - 재귀

Code States
Front-end boost camp
Today
I
Learned

🧢 41일차.. 재귀와 알고리즘..!

---

🧢 재귀

• 원래의 자리로 되돌아가거나 되돌아옴
• 재귀 함수란? 자기 자신을 호출하는 함수
• 재귀를 사용하기 적합한 상황은?
  -- 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
  -- 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
  -- 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

🧢 재귀로 문제 해결하기

• 어떤 문제를 반복문으로 해결하는 방법도 있지만, 재귀로 해결할 수도 있다.
• 방법
  -- 1) 문제를 좀 더 작게 쪼갠다
  -- 2) 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갠다.
  -- 3) 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.
• 문제를 작게 쪼개는 것 : recursive case
• 재귀의 탈출 조건과 관련 있는 것 : base case
• 예시 ▼

// 문제 : 자연수를 입력받고, 입력받은 수부터 1까지의 자연수를 모두 곱한 값을 리턴하는 재귀 함수 `fac` 을 작성하세요.

// 예제 1)
fac(5)  ===  5 * 4 * 3 * 2 * 1  ===  120

// 예제 2)
fac(3)  ===  3 * 2 * 1  ===  6

🧢 재귀 문제풀이

• 문제1) sumTo
  

function sumTo(num) {
  // TODO: 여기에 코드를 작성합니다.
  // 별도의 최적화 기법(memoization)은 금지됩니다.
  if (num <= 1) {
    return num;
  }
  return num + sumTo(num-1);
}

• 문제2) isOdd
  

function isOdd(num) {
  // TODO: 여기에 코드를 작성합니다.
  if (num === 0) {
    return false;
  } else if (num === 1) {
    return true;
  }

  if (num < 0) {
    return isOdd(-num);
  }

  return isOdd(num - 2);
}

• 문제3) factorial
  

function factorial(num) {
  // TODO: 여기에 코드를 작성합니다.
  // 별도의 최적화 기법(memoization)은 금지됩니다.
  if (num === 1 || num === 0) {
    return 1
  }
  return num * factorial(num - 1);
}

• 문제4)
  

function fibonacci(num) {
  // TODO: 여기에 코드를 작성합니다.
  // 별도의 최적화 기법(memoization)은 금지됩니다.
  if (num === 0) {
    return 0
  } else if (num === 1) {
    return 1
  }

  return fibonacci(num - 1) + fibonacci(num - 2);
}

• 문제5)
  

function arrSum(arr) {
  // TODO: 여기에 코드를 작성합니다.
  let n = arr.length;

  if (n === 0) {
    return 0
  } 
  
  const head = arr[0];
  const tail = arr.slice(1);
  return head + arrSum(tail);
}

• 문제6)
  

function arrProduct(arr) {
  // TODO: 여기에 코드를 작성합니다.
  if (arr.length === 0) {
    return 1;
  }

  const head = arr[0];
  const tail = arr.slice(1);
  return head * arrProduct(tail);
}

• 문제7)
  

function arrLength(arr) {
  // TODO: 여기에 코드를 작성합니다.
  if (arr.isEmpty() === true) {
    return 0
  }
  
  const tail = arr.slice(1);
  return 1 + arrLength(tail);
}

• 문제8)
  

function drop(num, arr) {
  // TODO: 여기에 코드를 작성합니다.
  if (num === 0 || arr.length === 0) {
    return arr;
  }

  const tail = arr.slice(1);
  return drop(num - 1, tail);
}

• 문제9)
  

function take(num, arr) {
  // TODO: 여기에 코드를 작성합니다.

  if (num === 0 || arr.length === 0) {
    return [];
  }

  const head = arr[0];
  const tail = arr.slice(1);
  return [head].concat(take(num - 1, tail));
}

• 문제10)
  

function and(arr) {
  // TODO: 여기에 코드를 작성합니다.
  if (arr.length === 0) {
    return true
  }

  const head = arr[0];
  const tail = arr.slice(1);
  
  return head && and(tail);
}

• 문제11)
  

function or(arr) {
  // TODO: 여기에 코드를 작성합니다.
  if (arr.length === 0) {
    return false;
  }

  const head = arr[0];
  const tail = arr.slice(1);
  return head || or(tail);
}

• 문제12)
  

function reverseArr(arr) {
  // TODO: 여기에 코드를 작성합니다.
  if (arr.length === 0) {
    return [];
  }

  const head = arr[0];
  const tail = arr.slice(1);
  return reverseArr(tail).concat(head)
}

• 문제13) 업데이트 중...
  

function findMatryoshka(matryoshka, size) {
  // TODO: 여기에 코드를 작성합니다.
  if (Object.keys(matryoshka).length === 0) {
    return false;
  } else {
    
    if (matryoshka.size === size) {
      return true;
    }
    else if (matryoshka.matryoshka && matryoshka.size > size) {
      return findMatryoshka(matryoshka.matryoshka, size)
    }
    else return false;
  }
}

• 문제14)
  -- flat함수도 가능은 할 것 같은데 테스트 통과가 안됨
  

function unpackGiftbox(giftBox, wish) {
  // recursive case
  for (let i = 0; i < giftBox.length; i++) {
    if (giftBox[i] === wish) {
      return true;
    } else if (Array.isArray(giftBox[i])) {
      const result = unpackGiftbox(giftBox[i], wish);
      if (result === true) {
        return true;
      }
    }
  }

  // base case
  return false;
}

• 문제15)
  

function flattenArr(arr) {
  // base case
  if (arr.length === 0) {
    return [];
  }

  // recursive case
  const head = arr[0];
  const tail = arr.slice(1);
  if (Array.isArray(head)) {
    return flattenArr([...head, ...tail]);
  } else {
    return [head].concat(flattenArr(tail));
  }
}

🧢 41일차 수업을 마치며...

리액트 보단 알고리즘 푸는게 낫다... ㄷㄷ 어렵지만 어찌 이런 생각을 해냈는지 신기해... 과거 수학자들과 이 내용을 프로그래밍에 이용하는 개발자들에 경외심이 생겨버릠,,