재귀함수

• 자기 자신을 호출하는 함수
• 반복문 <-> 재귀함수
  - 반복문을 표현할수 있는 것들은 재귀함수로 표현할수있다.
• 재귀함수는 종결조건이 필수!!
  - 종결조건이 없으면 무한루프에 빠지게 된다.

예제

function f(n) {
  // 종결조건
  if (n <= 1) {
    return 1;
  }
  
  return n + f(n-1);
}

순번	f(n)	n	return	최종
1	f(100)	100	100 + f(99)	100+99+98+..+2+1
2	f(99)	99	99 + f(98)	99+98+97..+2+1
3	f(98)	98	98 + f(97)	98+97+96..+2+1
...	-	-	-	-
99	f(2)	2	2 + f(1)	2+1
100	f(1)	1	1	1

2진수 변환

not recursive

const getBinaryNum = (num) => {
 let result = '';
 let n = num;
 while(true) {
   n % 2 === 0 ? result += '0' : result += '1';
   n = Math.floor(n / 2);
   if (n < 2) {
     result += String(n);
     break;
   }
   
   return parseInt(result.split('').reverse().join(''), 10);
 };
 console.log(getBinaryNum(11)); // 1011

recursive

const getRecursiveBinaryNum = (num) => {
  if (num < 2) {
    return String(num);
  };
  
  return getRecursiveBinaryNum(Math.floor(num / 2)) + String(num & 2);
};
console.log(getRecursiveBinaryNum(11)); // '11'

순번	f(n)	n	return	최종
1	getRecursiveBinaryNum(11)	11	getRecursiveBinaryNum(Math.floor(11 / 2)) + '1'	'101'+'1'
2	getRecursiveBinaryNum(5)	5	getRecursiveBinaryNum(Math.floor(5 / 2)) + '1'	'10'+'1'
3	getRecursiveBinaryNum(2)	2	getRecursiveBinaryNum(Math.floor(2 / 2)) + '0'	'1'+'0'
4	getRecursiveBinaryNum(1)	1	'1'	'1'