알고리즘 & 자료구조 스터디 6주차 [재귀]

May 10, 2023 🐰

🤯 오늘 배울 개념은 재귀!

🔑 재귀(Recursion)

• 어떤 종료점에 도달할 때까지 더 작은부분이나 변경되는 부분에서 반복으로 수행하는 것이다.

objectives

• 재귀가 무엇이고 어떻게 유용한지를 정의한다.
• 재귀함수 작성의 두가지 핵심 구성요소를 이해한다.
• 호출 스택이라는 걸 배울예정
• 헬퍼 메소드 재귀와 순수 재귀에 대해서 공부해보자고!

배워야하는 이유 :

- (JSON.parse / JSON.stringify)
- document.getElementById and Dom traversal
- Object traversal
- cleaner alternative to iteration

함수 호출

호출 스택 (call stack) 스택의 개념으로 재귀는 작동한다.
호출스택에서 재귀는 계속해서 쌓인다.

🔑 재귀를 만들어보자!

재귀함수의 두가지 기본요소

• 라인을 끝내는 종료
• 조건다른 입력값

👩🏻‍🌾 An Example Recursion

재귀는 종료조건을 찾거나 return 을 주의해서 문제들을 해결해야 한다.

*재귀 솔루션을 작성할 때 흔히 발생하는 문제들*
- no base case  종료조건이 없는 것
- forgetting to return or returning the wrong thing 값을 반환하는 걸 잊는것, 잘못된 값을 반환하는 것
- stack overflow! ⇒ 재귀가 멈추지 않아서 발생하는 경우임

👩🏻‍🌾count Down

function countDown(num) {
  if (num <= 0) {
    console.log("All done!!");
    return;
  }
  console.log(num);
  num--;
  countDown(num);
}

countDown(10);

👩🏻‍🌾 Sum Range

function sumRange(num) {
  console.log(num);
  if (num === 1) return 1;
  return num + sumRange(num - 1);
}
let r = sumRange(10);
console.log(r);

👩🏻‍🌾 Factorial

👩🏻‍🌾반복문

 function factorial(num) {
   let total = 1;
   for (let i = num; i > 0; i--) {
     total *= i;
   }
   return total;
 }

👩🏻‍🌾재귀

function factorial(num) {
  if (num === 1) return 1;
  return num * factorial(num - 1);
}

let total = factorial(4);
console.log(total);

👩🏻‍🌾 Helper Method

• 외부에서 result나 결과값을 불러오는 것을 방지하기 위해 함수 내에 실행시켜 결과값을 저장하여 재귀를 반복할 수 있는 방식

function collectOddValues(arr) {
  let result = [];

  function helper(helperInput) {
    if (helperInput.length === 0) {
      return;
    }
    if (helperInput[0] % 2 !== 0) {
      result.push(helperInput[0]);
    }
    helper(helperInput.slice(1));
  }
  helper(arr);
  return result;
}

🔑 문제를 많이 풀어보자!

👩🏻‍🌾 Coding Exercise 10 : power

• solution과 비슷

function power(a, b) {
  if (b === 0) return 1;
  else return a * power(a, b - 1);
}

power(2, 0);
power(2, 2);
let r = power(2, 4);
console.log(r);

👩🏻‍🌾 Coding Exercise 11 : factorial

• 강의에서 배운거와 같다

function factorial(num) {
  if (num <= 1) return 1;
  return num * factorial(num - 1);
}

let r = factorial(7);
console.log(r);

👩🏻‍🌾 Coding Exercise 12 : productOfArray

배열의 값들을 다 곱하는 문제
// productOfArray([1,2,3]) // 6
// productOfArray([1,2,3,10]) // 60

return 첫번째 값 * (재귀 [ 첫째 값 삭제] )

function productOfArray(arr) {
  if (arr.length === 0) return 1;
  else return arr[0] * productOfArray(arr.slice(1));
}

let r = productOfArray([1, 2, 3, 10]);
console.log(r);

👩🏻‍🌾 Coding Exercise 13 : recursiveRange

// SAMPLE INPUT/OUTPUT
// recursiveRange(6) // 21
// recursiveRange(10) // 55 
간단한 1~대입값까지 더하는 과정

function recursiveRange(num) {
  if (num === 0) return 0;
  else return num + recursiveRange(num - 1);
}

let r = recursiveRange(10);
console.log(r);

👩🏻‍🌾 Coding Exercise 14 : fib

피보나치 수열을 구하는 것이다. 
이 문제를 응용해서 프로그래머스에 있는 문제를 풀어보니 재귀의 실행시간이 너무 길다.

오히려 for문으로 문제를 해결하는것이 좋아보인다.

프로그래머스 lv2 피보나치수열

function fib(num) {
  // add whatever parameters you deem necessary - good luck!

  if (num < 3) return 1;
  else return fib(num - 1) + fib(num - 2);
}

👩🏻‍🌾 Coding Exercise 15 : reverse

// reverse('awesome') // 'emosewa'
// reverse('rithmschool') // 'loohcsmhtir'

어렵게 느껴졌지만 맨뒤 값을 return을 할 때
return  [재귀 (맨앞 값 삭제)] + 첫째값 더하기

=> 자연스럽게 reverse가 된다.

function reverse(re) {
  if (re.length === 0) return re;
  return reverse(re.slice(1)) + re[0];
}

👩🏻‍🌾 Coding Exercise 16 : isPalindrome

// isPalindrome('awesome') // false
// isPalindrome('foobar') // false
// isPalindrome('tacocat') // true
// isPalindrome('amanaplanacanalpanama') // true
// isPalindrome('amanaplanacanalpandemonium') // false

첫 값과 맨 끝값을 계속 비교하면서 처음과 끝을 삭제해준다.
끝까지 같으면 true를 반환

function isPalindrome(str) {
  // add whatever parameters you deem necessary - good luck!
  if (str.length <= 1) return true;

  if (str[0] === str[str.length - 1]) {
    return isPalindrome(str.slice(1, str.length - 1));
  } else return false;
}

isPalindrome("awesome"); // false
isPalindrome("foobar"); // false
let r = isPalindrome("tacocat"); // true
isPalindrome("amanaplanacanalpanama"); // true
isPalindrome("amanaplanacanalpandemonium"); // false

console.log(r);

💻 Source

• ✏️ Best JavaScript Data Structures & Algorithms Course by Udemy, last updated January 2022, accessed April 5, 2023 - https://www.udemy.com/
• ⌨️ reference gitHub - https://github.com/seunghyun0522/JavaScript-Algorizms-Data-Structure