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

 

재귀(recursion, 再歸) 함수

: 자기 자신을 호출하는 함수

 

 

 

[ 재귀로 문제를 해결하는 단계 ]

 

1. 문제를 좀 더 작게 쪼갠다.

2. 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갠다.

3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.

 

//자연수로 이루어진 배열을 입력받아, 리스트의 합을 리턴하는 함수 'arrSum'을 만들어보자.


//1.문제를 작게 쪼개기 (예) [1, 2, 3, 4, 5]
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5])
...


//2.문제를 가장 작은 단위로 쪼개기
...
arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])


//3.문제 해결하기
arrSum([]) === 0; // <-- 문제가 더는 작아지지 않는 순간
arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5;
arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9;
arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12;
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14;
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15;


//결과
function arrSum (arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드 (재귀의 기초 & 탈출 조건)
  if (arr.length === 0) {
    return 0
  }

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr.shift() + arrSum(arr)
}


//다른 풀이
function arrSum(arr) {
  if (arr.length === 0) {
    return 0;
  }

  // const [head, ...tail] = arr;
  const head = arr[0];
  const tail = arr.slice(1);
  return head + arrSum(tail);
}

 

(참고) shift() : 배열에서 첫 번째 요소를 제거하고, 제거된 요소를 반환하는 메서드.

                       이 메서드는 배열의 길이를 변하게 한다.

/* mdn 예제 */
const array1 = [1, 2, 3];

const firstElement = array1.shift();

console.log(array1);
// Expected output: Array [2, 3]

console.log(firstElement);
// Expected output: 1

 

 

 

→ 재귀를 사용하는 이유?

 

모든 재귀함수는 반복문으로 표현할 수 있지만, 재귀를 사용하는 경우 코드가 더욱 간결해진다. 

 

 

 

→ 언제 사용하는 게 좋을까?

 

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

 

 

 

---

 

 

★★★★★★★★★★★★★★★★★★★★★★★★★

 

/* 일반적인 재귀 함수의 템플릿 */

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

 

★★★★★★★★★★★★★★★★★★★★★★★★★

 

 

 

 

//문제 : 자연수(양의 정수)를 입력받아, 입력받은 수부터 1까지의 자연수를 모두 곱한 값을
//       리턴하는 재귀 함수 `fac`을 만들어보자. (팩토리얼)

function fac(n) {
  if (n === 1) {
    return 1;
  }
  return n * fac(n - 1);
}

 

 

---

 

 

>> 코플릿 문제 복기

      ※ 반복문(for, while) 사용 금지

      ※ 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 함(immutability)

 

 

 

Q. 수를 입력받아 홀수인지 여부(boolean 타입)를 리턴해야 합니다.

     ※  나눗셈(/), 나머지(%) 연산자 사용 금지

     ※  0은 짝수로 간주

//나의 풀이

function isOdd(num) {
  //나눗셈을 못 쓰면, 계속 2를 빼볼까?
  num = Math.abs(num);  //절대값 씌워서 음수인 경우 해결.
  if(num === 0){  //나머지가 0이면,
    return false;
  }
  if(num === 1){  //나머지가 1이면,
    return true;
  }
  return isOdd(num - 2);
}

 

//레퍼런스 풀이

function isOdd(num) {
  if (num === 0) {
    return false;
  } else if (num === 1) {
    return true;
  }

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

 

 

 

Q. 수(num)를 입력받아 피보나치 수열의 num번째 요소를 리턴해야 합니다.

     ※ 피보나치? -> 0, 1, 1, 2, 3, 5, 8, 13 ···

function fibonacci(num) {

  // 0 n 0+n
  //   n 0+n 0+n+n
  //     0+n 0+n+n 0+n+n+n
  
  if(num === 0){
    return 0
  }
  if(num === 1){
    return 1
  }
  
  // 위 base case를 레퍼런스 풀이에선 아래와 같이 작성하였다.
  // if (num <= 1) {
  //   return num;
  // }

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

 

Q. 배열을 입력받아 그 길이를 리턴해야 합니다. 

     ※ arr.length 사용은 금지

function arrLength(arr) {  //[1, 2, 3, 4]
  if(arr.isEmpty() === true){  //이 문제에서만 쓰는 배열이 비어있는지 확인할 수 있는 메서드
    return 0;
  }
  // const [head, ...tail] = arr;
  const tail = arr.slice(1);
  return 1 + arrLength(tail);  
  
  //1 + [2, 3, 4]
  //1 + 1 + [3, 4]
  //1 + 1 + 1 + [4]
  //1 + 1 + 1 + 1
}

 

 

 

Q. 수(num)와 배열을 입력받아 차례대로 num개의 요소가 제거된 새로운 배열을 리턴해야 합니다.

function drop(num, arr) {  //2, [1, 2, 3, 4, 5] -> [3, 4, 5]

  // num과 arr.length 중 최소값만큼 제거
  // if (num >= arr.length) {
  //   return [];
  // }
  
  if(arr.length === 0 || num === 0){  //탈출 조건
    return arr;
  }
  const tail = arr.slice(1);
  return drop(num - 1, tail);  
  //1, [2, 3, 4, 5]
  //0, [3, 4, 5]
}

 

 

 

Q. 수(num >= 0)와 배열을 입력받아 차례대로 num개의 요소만 포함된 새로운 배열을 리턴해야 합니다.

function take(num, arr) {  //2, [1, 2, 3, 4, 5] -> [1, 2]
  // TODO: 여기에 코드를 작성합니다.
  if(arr.length === 0 || num === 0 ){  
    return [];
  }
  const head = arr[0]; //slice(0, 1)을 써도 됨. [1]
  const tail = arr.slice(1);  //[2, 3, 4, 5]
  return [head].concat(take(num-1,tail));  //[1] + [2]
}

 

 

 

Q. (boolean 타입을 구성 요소로 갖는) 배열을 입력받아 모든 요소의 논리곱(and)을 리턴해야 합니다.

    ※ boolean 타입을 리턴

function and(arr) {  //false가 하나라도 있으면 false
  if(arr.length === 0) {  //빈 배열의 논리곱은 true
    return true;
  }
  const head = arr[0];
  const tail = arr.slice(1);
  if(head === true){
    return and(tail);
  }
  return false;
}


//논리합(or)의 경우
function or(arr) {
  if(arr.length === 0){
   return false;
  } 
  const head = arr[0];
  const tail = arr.slice(1);
  if(head === false){
    return or(tail);
  }
  return true
}

 

 

 

Q. 배열을 입력받아 순서가 뒤집힌 배열을 리턴해야 합니다.

function reverseArr(arr) {  //[1, 2, 3, 4]
  if(arr.length === 0) {
    return [];
  }
  const head = arr[0];  //[1]
  const tail = arr.slice(1);  //[2, 3, 4]
  return reverseArr(tail).concat(head);  //[4]+[3]+[2]+[1]
}

 

 

 

Q. 마트료시카에 대한 정보를 담은 객체와 수를 입력받아 조건에 맞는 인형이 있는지 여부를 리턴해야 합니다.

     ※ matryoshka.matryoshka는 null 또는 matryoshka 객체

     ※ matryoshka.size는 중첩될수록 작아짐

     ※ boolean 타입을 리턴

     ※ 빈 객체를 입력받은 경우, false를 리턴

/* 입출력 예시 -> 재귀적으로 정의된 객체 */

// const matryoshka = {
//   size: 10,
//   matryoshka: {
//     size: 9,
//     matryoshka: null,
//   },
// };

// let output = findMatryoshka(matryoshka, 10);
// console.log(output); // --> true

// output = findMatryoshka(matryoshka, 8);
// console.log(output); // --> false



function findMatryoshka(matryoshka, size) {
  if(matryoshka.size === size){  //내가 찾던 사이즈 발견!
    return true;
  }
  if(matryoshka.matryoshka) {  
    //마트료시카 안의 마트료시카를 열어보는 경우?
    //마트료시카 안에 마트료시카가 있을 때
    return findMatryoshka(matryoshka.matryoshka, size)
  } //내가 찾고 있는 사이즈 자체는 변하지 않는다.
  return false;  //다 까봤는데 없어..
}

 

 

 

Q. 선물 상자에 대한 정보를 담은 배열과 문자열을 입력받아 조건에 맞는 선물이 있는지 여부를 리턴해야 합니다.

    ※ 배열은 더 작은 선물 상자를 의미함

    ※ boolean 타입을 리턴

    ※ 빈 배열 또는 빈 문자열을 입력받은 경우, false를 리턴

/* 입출력 예시 -> 재귀적으로 정의된 배열 */

// const giftBox = ['macbook', 'mugcup', ['eyephone', 'postcard'], 'money'];

// let output = unpackGiftbox(giftBox, 'iphone');
// console.log(output); // --> false

// output = unpackGiftbox(giftBox, 'postcard');
// console.log(output); // --> true



//겹겹이 쌓여 있는 경우도 있을 수 있어(몇 겹인지 모름) 반복문으로 풀기 어렵다. 
//이중 반복문을 넘어갈 수 있음

function unpackGiftbox(giftBox, wish) {
  for(let i = 0; i < giftBox.length; i++){
    if(giftBox[i] === wish){
      return true
    }
    if(Array.isArray(giftBox[i])){  //더 작은 선물상자가 나왔을 때
      const result = unpackGiftbox(giftBox[i],wish)
      //바로 리턴하면 안됨. 리턴하는 순간 다음으로 넘어가지 않고 과정이 끝나기 때문
      if(result === true){
        return true
      }
    }
  }
  return false;
}



//같은 풀이법, but 다른 작성법

function unpackGiftbox(giftBox, wish) {
  for(let gift of giftBox){
      if(gift === wish){
       return true
    }
    if(Array.isArray(gift)){
      if(unpackGiftbox(gift, wish) === true){
        return true
      }
    }
  }
  return false;
}

 

 

 

Q. 다차원 배열을 입력받아 1차원 배열로 변환하여 리턴해야 합니다.

     ※ Array Method flat()과 flatMap() 사용은 금지

     ※ 입력으로 전달되는 다차원 배열이 중첩된 정도(중첩의 깊이)는 정해져 있지 않음

     ※ 빈 배열을 입력받은 경우, 빈 배열을 리턴

/* 입출력 예시 */

// let output = flattenArr([[1], 2, [3, 4], 5]);
// console.log(output); // --> [1, 2, 3, 4, 5]

// output = flattenArr([[2, [[3]]], 4, [[[5]]]]);
// console.log(output); // --> [2, 3, 4, 5]



//풀이1
function flattenArr(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {  //배열을 순회하면서
    if (Array.isArray(arr[i]) === true) {  //인자가 배열인 경우,
      const arr2 = flattenArr(arr[i]);
      result.push(...arr2);  //풀어 넣어
    } else {
      result.push(arr[i]);  //아니면 그냥 넣어
    }
  }
  return result;
}


//풀이2
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));
  }
}


//풀이3
function flattenArr(arr) {
  return arr.reduce(function (result, item) {
    if (Array.isArray(item)) {
      const flattened = flattenArr(item);
      return [...result, ...flattened];
    } else {
      return [...result, item];
    }
  }, []);
}

 

//세션 때 풀이
function flattenArr(arr) {  //[0, [1], 2, [3, 4], 5]
  for (let i = 0; 1 < arr.length; i++){
    if(Array.isArray(arr[i])){  //배열인 요소 발견!
      let front = arr.slice(0, i)  //앞에 있는 친구들 -> [0]
      let middle = arr[i]          //풀어줘야 하는 친구 -> [1]
      let back = arr.slice(i + 1)  //뒤에 있는 친구들 -> [2, [3, 4], 5]

      return flattenArr([...front, ...middle, ...back]);  //[0, 1, 2, [3, 4], 5]
    }
  }
  return arr;
}
// -> 테스트를 돌리면 시간이 초과되었다고 뜨는 문제가 있음.

 

 

 

( + ) https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/slice

Array.prototype.slice() - JavaScript | MDN