자바스크립트로 하는 자료구조와 알고리즘(8장) - 재귀

무한 재귀 호출은 스택 오버플로를 초래한다.

 

기저 조건

  = 종료조건, 재귀를 탈출하기 위한 조건이라고 보면 된다.

 

대표예시

 

피보나치 수열

 

일반 반복문으로 구현한 피보나치수열

function getNthFibo(n) {
  if ( n <= 1) return n;
  let sum = 0;
  let last = 1;
  let lastlast = 0;

  for (let i = 1; i < n; i++) {
    sum = lastlast + last;
    lastlast = last;
    last = sum;
  }

  return sum;
}

console.log(getNthFibo(8));

 

재귀 함수로 구현

function getNthFibo(n) {
  if ( n <= 1) {
    return n;
  } else {
    return getNthFibo(n-1) + getNthFibo(n - 2);
  }
}

console.log(getNthFibo(8));

기저 조건 : 첫번째항목이 1인 경우

위 방법의 시간복잡도는 O(2^n)이다. 

 

function getNthFibo(n, lastlast, last) {
  if ( n  === 0) {
    return lastlast;
  } 
  if (n === 1) {
    return last;
  }
  else {
    return getNthFibo(n-1, last, lastlast + last);
  }
}

console.log(getNthFibo(8, 0, 1));

시간복잡도 O(n)이다.

 

 

파스칼의 삼각형

 

기저조건 : 최상위 항목 1의 경우임

function pascalTriangle(row, col) {
  if ( col  === 0) {
    return 1;
  } else if (row === 0) {
    return 0;
  } else {
    return pascalTriangle(row -1, col) + pascalTriangle(row - 1, col - 1);
  }
}

console.log(pascalTriangle(5, 2));

 

 

연습문제

 

십진수를 이진수로 변환하기

 

십진수를 이진수로 변환하기 위해서는 숫자를 계속해서 2로 나누고 매번 나머지와 나눗셈을 계산해야함!

기저 조건 : n이 2보다 작을 때 

function base10ToString(n) {
  let binaryString = "";

  function base10ToStringHeplper(n) {
    if(n < 2){
      binaryString += n;
      return;
    } else {
      base10ToStringHeplper(Math.floor(n/2));
      base10ToStringHeplper(n%2);
    }
  }
  base10ToStringHeplper(n);

  return binaryString;
}

console.log(base10ToString(232));

시간복잡도 : O(log2(n)) 시간

 

 

배열의 모든 순열 출력하기

 

기저조건 : beginIndex가 endIndex와 동일하다. => 현재 순열을 출력한다.

항목들을 교환하기 위한 함수가 따로 필요!

 

function swap(strArr, index1, index2) {
  let temp = strArr[index1];
  strArr[index1] = strArr[index2];
  strArr[index2] = temp;
}

function permute(strArr, begin, end) {
  if(begin === end) {
    console.log(strArr);
  } else {
    for (let i = begin; i < end + 1; i++){
      swap(strArr, begin, i);
      permute(strArr, begin + 1, end);
      swap(strArr, begin, i);
    }
  }
}

function permuteArray(strArr) {
  permute(strArr, 0, strArr.length-1);
}

permuteArray(["A","C","D"]);

 

시간 복잡도는 O(n!)이다.

 

 

객체 펼치기

 

let dictionary = {
  'Key1' : '1',
  'Key2' : {
    'a' : '2',
    'b' : '3',
    'c' : {
      'd' : '3',
      'e' : '1'
    }
  }
}

function flattenDictionary(dictionary) {
  let flattenDictionary = {};

  function flattenDictionaryHelper(dictionary, propName){
    if (typeof dictionary !== 'object') {
      flattenDictionary[propName] = dictionary;
      return;
    }
    for (let prop in dictionary) {
      if(propName === '') {
        flattenDictionaryHelper(dictionary[prop], propName+prop);
      } else {
        flattenDictionaryHelper(dictionary[prop], propName+'.'+prop);
      }
    }
  }
  flattenDictionaryHelper(dictionary, '');
  return flattenDictionary;
}

console.log(flattenDictionary(dictionary));

시간 복잡도는 O(n)

 

 

문자열이 거꾸로 읽어도 동일한지 여부를 재귀적으로 결정하는 프로그램 작성하기

 

 

function isPalindromeRecursive(word) {
  return isPalindromeRecursiveHelper(word, 0, word.length-1);
}

function isPalindromeRecursiveHelper(word, beginPos, endPos) {
  if(beginPos >= endPos) {
    return true;
  }
  if(word.charAt(beginPos) !== word.charAt(endPos)) {
    return false;
  } else {
    return isPalindromeRecursiveHelper(word, beginPos + 1, endPos - 1);
  }
}

console.log(isPalindromeRecursive('racecar'));

시간 복잡도 O(n) 이다.