재귀

재귀 호출은 운영체제의 메모리 스택에 저장돼야 하는데, 재귀함수는 이러한 재귀 호출로 인해 발생하는 추가적인 공간 복잡도 비용을 지닌다.

피보나치수열

기본

function getNthFibo(n) {
    if (n <= 1) return n;

    var sum = 0,
        last = 1,
        lastlast = 0;

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

재귀

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

향상

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

for (var i=1; i < 10; i++) {
    console.log(getNthFiboBetter(i,0,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);
  }
}
pascalTriangle(5, 2); // 10

 

10진수를 2진수로

그냥

function decimalToBinary(n) {
  var binary = "";
  while (n >= 2) {
    binary += n % 2;
    n = Math.floor(n / 2);
  }
  binary += 1;
  return (binary = binary.split("").reverse().join(""));
}

console.log(decimalToBinary(17));

재귀

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

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

    return binaryString;
}

console.log(base10ToString(232)); // 11101000

배열의 모든 순열 출력하기 n개중에 n개 선택하는 경우 출력

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

function permute(strArr, begin, end) {
  if (begin == end) {
      console.log(strArr);
  } else {
      for (var 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"]);

객체 펼치기

var dictionary = {
  Key1: "1",
  Key2: {
    a: "2",
    b: "3",
    c: {
      d: "3",
      e: "1",
    },
  },
};
function flattenDictionary(dictionary) {
  var flattenedDictionary = {};

  function flattenDitionaryHelper(dictionary, propName) {
    if (typeof dictionary != "object") {
      flattenedDictionary[propName] = dictionary;
      return;
    }
    for (var prop in dictionary) {
      if (propName == "") {
        flattenDitionaryHelper(dictionary[prop], propName + prop);
      } else {
        flattenDitionaryHelper(dictionary[prop], propName + "." + prop);
      }
    }
  }

  flattenDitionaryHelper(dictionary, "");
  return flattenedDictionary;
}
flattenDictionary(dictionary);

 

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

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

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

isPalindromeRecursive('hi'); // false
isPalindromeRecursive('iii'); // true
isPalindromeRecursive('ii'); // true
isPalindromeRecursive('aibohphobia'); // true
isPalindromeRecursive('racecar'); // true