recursion 코드 예시

카운트다운

let countDownFrom = (num) => {
    if(num===0) return;
    countDownFrom(num-1)
}

 

팩토리얼

factorial(5) // 120

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

 console.log(factorial(5)); 

factorial(5)
  => 5 * factorial(5 - 1)
    => 4 * factorial(4 - 1)
      => 3 * factorial(3 - 1)
        => 2 * factorial(2 - 1)
          => 1
        => 2 * 1
      => 3 * 2
    => 4 * 6
  => 5 * 24
=> 120

https://davidtang.io/2019/03/26/learning-recursion-in-javascript-part-1.html

피보나치(클로저 사용)

function makeFib() {
    var num = 0;	// 함수가 호출될때 마다 카운트
    function fibo(n){
      if(n<2) return n
      return fibo(n-1) + fibo(n-2)  
    }
    return function(){
      num++;	// 카운트 
      return fibo(num-1);	// fibo함수가 0부터 시작하기위해 -1을 해줌
    }
}
var fn = makeFib()

 

메모이제이션 활용

function fibo(){
    let fib0 = 0;
    let fib1 = 0;
    
    return function(){
    	if(fib1 === 0){
            fib1 = 1;
            return 0;
        }
        let prefib0 = fib0;
        let prefib1 = fib1;
        
        fib0 = prefib1;
        fib1 = prefib0 + prefib1;
        
        return fib0;
     }
}

let fib = fibo();

 

문자열반복

function repeatString(string, times) {
  if (times < 0) {
    return "";
  }
  if (times === 1) {
    return string;
  } else {
    return string + repeatString(string, times - 1); // return "abcabcabc";
  }
  /* 
    First Part of the recursion method
    You need to remember that you won’t have just one call, you’ll have several nested calls
                     times       string + repeatString(string, times - 1)
      1st call         3                 "abc" + ("abc", 3 - 1)
      2nd call         2                 "abc" + ("abc", 2 - 1)
      3rd call         1                 "abc" => if (times === 1) return string;
      4th call         0                  ""   => if (times <= 0) return "";
    Second part of the recursion method
      4th call will return      ""
      3rd call will return     "abc"
      2nd call will return     "abc"
      1st call will return     "abc"
    The final call is a concatenation of all the strings
    return "abc" + "abc" + "abc"; // return "abcabcabc";
  */
}
repeatString("abc", 3);

 

숫자 String만들기

function makeNumberString (current, max, initialString) {
  var str = initialString || ""; // maybe I don't have one yet
  var currentString = str.concat(current.toString());

  if (current > max) {
    return initialString;
  }
  return makeNumberString(current + 1, max, currentString);
}

makeNumberString(0, 9);

 

Sum

sum([1, 2, 3, 4, 5, 6]) // 21

var sum = function(arr){
    if(arr.length === 0){
    	return 0;
    } else {
    	return array[0] + sum(array.slice(1));
    }
};

https://davidtang.io/2019/03/31/learning-recursion-in-javascript-part-2.html

function sum(arr) {
    if(arr.length === 0) return 0;
    let[head,...tail] === arr;
    return head + sum(tail)
}

 

Sum(nested arrays)

arrSum([1,[2,3],[[4]],5]) // 15

function arrSum(arr){
	let result = 0;
    if(arr.length === 0){
    	return 0;
    } else {
    	arr.forEach(function(ele){
        	if(Array.isArray(ele)){
            	result += arraySum(ele);
            } else if(typeof ele === 'number'){
            	return result += ele
            }
        });
        return result;
    }
}

 

Flatten

function flatten(nestedArr, result){
	let result = [];
    function checkNest(nestedArr){
    	for(let i = 0; i < nestedArr.length; i++){
        	if(Array.isArray(nestedArr[i])){
            	checkNest(nestedArr[i])
            } else {
            	result.push(nestedArr[i])
            }
         }
      }
   checkNest(nestedArr)
   return result
}

https://davidtang.io/2019/04/05/learning-recursion-in-javascript-part-3.html

 

Range

range(2, 9) // [3, 4, 5, 6, 7, 8]

function range(start, end) {            
    if(start === end){
        return end;
    } else if(start > end){
        return [];
    } else {
        return [start].concat(range(++start, end));
    } 
}

console.log(range(4, 15));

 

var range = function(x, y){
	if(y-x === 2){
    	return [x+1];
    } else {
    	var list = range(x, y-1);
        list.push(y-1);
        return list;
    }
};

 

var range = (a, b, arr) => {
    arr.push(++a);
    if (a === b - 1) return arr;

    return range(a, b, arr);
}

 

function range(a,b){
	var m = a;
	if(a !== b-1){
	   c.push(++m);
	   return range(++a,b);
	} else {
	return c;
}

 

지수구하기

exponent(4,3) // 64

var exponent = function(base, exp){
	if(exp === 0) { return 1;}
    return base*exponent(base,exp-1);
}

 

최대공약수 

var gcd = function(a, b) {
    if (b === 0) { return a;}
    return gcd(b, a % b);
};

 

최대공약수(유클리드 호제법 사용)

function uclid(m,n){
    if(n===0) {
    	return m;
    }
    if(m % n === 0){
    	return n;
    } else if(m % n !== 0){
    	return uclid(n, m%n);
    }
}

 

2의 거듭제곱인지 확인하기

powerOfTwo(1) // true

powerOfTwo(10) // false

var powerOfTwo = function(n) {
    var result = n/2;
    if(result < 2){ return false; }
    else if(result ===2) { return true; }
    else { return powerOfTwo(result)}
    };

 

Palindrome

var palindrome = function(string) {
    if(string.length === 0 || string.length === 1){
    	return true;
    } else if(string[0] === string[string.length-1] {
    	return palindrome(string.slice(1,string.length-1))
    }
    return false;
}

https://davidtang.io/2019/04/11/learning-recursion-in-javascript-part-4.html

곱하기

var multiply = function(x, y){
    if(y === 0){
    	return 0;
    } else {
    	return x + multiply(x, y-1);
    }
}

 

문자비교하기

var compareStr = function(str1, str2) {
    if(str1.length === 0 && str2.length === 0){
    	return true;
    } else if(str1[0] === str2[0]){
    	return compareStr(str1.slice(1), str2.slice(1))
    }
    return false;
}

 

각 문자열을 배열로 만들기

var createArray = function(str){
    var arr = [];
    if(str.length === 0) {
    	return arr;
    }
    arr.push(str[0]);
    arr = arr.concat(createArray(str.slice(1)));
    return arr;
}

 

배열의 순서 반대로하기

var reverstArr = function(arr) {
    var reversed = [];
    if(arr.length === 0) { return reversed;}
    reversed.push(arr.pop());
    reversed = reversed.concat(reverseArr(arr.slice(0)));
    return reversed;
}

 

해당 값과 길의를 가진 배열 만들기

buildList(0,5) // [0,0,0,0,0]

var buildList = function(val, leng){
	let arr = [];
    if(length === 0) {
    	return arr;
    }
    arr.push(val);
    return arr.concat(buildList(val,leng-1));
}

 

해당 값 몇번 존재하는지 확인하기

countOccurrence([2,7,4,4,1,4], 4) // 3

var countOccurrence = function(arr, val) {
	if(arr.length === 0) { return 0; }
    return (arr[0] === value) + countOccurrence(arr.slice(1), val);
};

 

재귀를 이용한 map 

var rMap = function(arr, callback) {
	if(arr.length === 1){
    	return callback(arr);
    }
    return [callback(arr[0])].concat(rMap(arr.slice(1), callback));
}

 

대문자로 바꾸기(첫글자만 대문자로 바꾸기(심화))

capitalizedWords(['i', 'am', 'learning', 'recursion']) // ['I', 'AM', 'LEARNING', 'RECURSION']

var capitalizeWords = function(input) {
	let result = [];
    if(input.length === 0){ return result; }
    result.push(input[0].toUpperCase());
    result = result.concat(capitalizeWords(input.slice(1)));
    return result;
};

 

글자수 세기 

letterTally('potato') // {'p':1, 'o':2, 't':2, 'a':1}

var letterTally = function(str, obj) {
	let result = Array.from(arguments) || {};
    if(str.length === 0) { return result; }
    if(!result[str[0]]) { result[str[0]] =1;}
    else { result[str[0]]++;}
    
    return letterTally(str.slice(1), resutl);
}

 

0없애기

minimizeZeroes([2,0,0,0,1,4]) // [2,0,1,4]

var minimizeZeroes = function(arr) {
	if(arr.length === 0){ return arr};
    if(minimizeZeroes(arr.slice(1))[0] === 0 && arr[0] === 0){
    	return minimizeZeroes(arr.slice(1));
    } else {
    	return [arr[0]].concat(minimizeZeroes(arr.slice(1)));
    }
};

 

+, - 교체

alternateSign([2,7,8,3,1,4]) // [2,-7,8,-3,1,-4]

var alternateSign = function(arr) {
    if(arr.length === 0) { return arr;}
    if(arr[0] < 0) { arr[0] = -arr[0]; }
    if(arr[1] > 0) { arr[1] = -arr[1]; }
    return [arr[0], arr[1]].concat(alternateSign(arr.slice(2));
 };