Recursion

Udemy - 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스

 

#Prac 10. power

Write a function called power which accepts a base and an exponent. The function should return the power of the base to the exponent. This function should mimic the functionality of Math.pow()  - do not worry about negative bases and exponents.

---

🅰️ (제출 답) ✅ (풀이 과정)

// power(2,0) // 1
// power(2,2) // 4
// power(2,4) // 16

function power(base, exponent){
    if(exponent === 0) return 1;
    return base * power(base, exponent -1);
    // base + base + base + base ...
}

---

#Prac 11. factorial

Write a function factorial which accepts a number and returns the factorial of that number. A factorial is the product of an integer and all the integers below it; e.g., factorial four ( 4! ) is equal to 24, because 4 * 3 * 2 * 1 equals 24.  factorial zero (0!) is always 1.

---

🅰️ (제출 답) ✅ (풀이 과정)

//factorial(1) // 1
// factorial(2) // 2
// factorial(4) // 24
// factorial(7) // 5040

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

🤼‍♀️  다른 풀이 1 (강의 솔루션)

    function factorial(x){
       if (x < 0 ) return 0;
       if (x <= 1 ) return 1;
       return x * factorial(x-1);
    }

=> params가 음수인 경우도 고려!!!!

---

#Prac 12. productOfArray

Write a function called productOfArray which takes in an array of numbers and returns the product of them all.

// productOfArray([1,2,3]) // 6
// productOfArray([1,2,3,10]) // 60

---

🅰️ (제출 답) ✅ (풀이 과정)

function productOfArray(arr){
    if(arr.length === 0) return 1;
    // arr[0] * arr[1] * ....
    return arr[0] * productOfArray(arr.slice(1));
}

🤼‍♀️  다른 풀이 1 (강의 솔루션)

위와 동일

---

#Prac 13. recursiveRange

Write a function called recursiveRange which accepts a number and adds up all the numbers from 0 to the number passed to the function 

// recursiveRange(6) // 21
// recursiveRange(10) // 55 

---

🅰️ (제출 답) ✅ (풀이 과정)

function recursiveRange(num) {
    // return num*(num+1)/2
    if(num === 0) return 0;
    return num + recursiveRange(num -1);
}

🤼‍♀️  다른 풀이 1 (강의 솔루션)

위와 동일

---

#Prac 14. fib

Write a recursive function called fib which accepts a number and returns the nth number in the Fibonacci sequence. Recall that the Fibonacci sequence is the sequence of whole numbers 1, 1, 2, 3, 5, 8, ... which starts with 1 and 1, and where every number thereafter is equal to the sum of the previous two numbers.

// fib(4) // 3
// fib(10) // 55
// fib(28) // 317811
// fib(35) // 9227465

---

🅰️ (제출 답) ✅ (풀이 과정)

function fib(num){
    if(num === 1) return 1;
    if(num === 2) return 1;
    //1, 1, 2, 3, 5, 8 ...
    //num = num -1 + num -2
    return fib(num -1) + fib(num -2)
}

🤼‍♀️  다른 풀이 1 (강의 솔루션)

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

---

---

#Prac 15. reverse

Write a recursive function called reverse which accepts a string and returns a new string in reverse.

// reverse('awesome') // 'emosewa'
// reverse('rithmschool') // 'loohcsmhtir'

---

🅰️ (제출 답) ✅ (풀이 과정)

function reverse(str){
    let result = "";
    function inner(x) {
        if(x.length === 0) return;
        result += x[x.length-1];
        inner(x.slice(0, x.length -1));
    }
    inner(str);
    return result;
}

🤼‍♀️  다른 풀이 1 (강의 솔루션)

    function reverse(str){
    	if(str.length <= 1) return str;
    	return reverse(str.slice(1)) + str[0];
    }

---

#Prac 16. isPalindrome

Write a recursive function called isPalindrome which returns true if the string passed to it is a palindrome (reads the same forward and backward). Otherwise it returns false.

// isPalindrome('awesome') // false
// isPalindrome('foobar') // false
// isPalindrome('tacocat') // true
// isPalindrome('amanaplanacanalpanama') // true
// isPalindrome('amanaplanacanalpandemonium') // false

---

🅰️ (제출 답) ✅ (풀이 과정)

function isPalindrome(str){
  if(str.length <= 1) return true; 
  if(str[0] !== str[str.length-1]){
      return false;
  }
  // console.log(str);
  return isPalindrome(str.slice(1, str.length -1))
}

🤼‍♀️  다른 풀이 1 (강의 솔루션)

    function isPalindrome(str){
        if(str.length === 1) return true;
        if(str.length === 2) return str[0] === str[1];
        if(str[0] === str.slice(-1)) return isPalindrome(str.slice(1,-1))
        return false;
    }

---

#Prac 17. someRecursive

Write a recursive function called someRecursive which accepts an array and a callback. The function returns true if a single value in the array returns true when passed to the callback. Otherwise it returns false.

// const isOdd = val => val % 2 !== 0;

// someRecursive([1,2,3,4], isOdd) // true
// someRecursive([4,6,8,9], isOdd) // true
// someRecursive([4,6,8], isOdd) // false
// someRecursive([4,6,8], val => val > 10); // false

---

🅰️ (제출 답) ✅ (풀이 과정)

function someRecursive(arr, callback){
    if(!arr.length) return false;
    if(callback(arr[0])) return true;
    return someRecursive(arr.slice(1), callback);
}

🤼‍♀️  다른 풀이 1 (강의 솔루션)

위와 동일

---

#Prac 18. flatten

Write a recursive function called flatten which accepts an array of arrays and returns a new array with all values flattened.

// flatten([1, 2, 3, [4, 5] ]) // [1, 2, 3, 4, 5]
// flatten([1, [2, [3, 4], [[5]]]]) // [1, 2, 3, 4, 5]
// flatten([[1],[2],[3]]) // [1,2,3]
// flatten([[[[1], [[[2]]], [[[[[[[3]]]]]]]]]]) // [1,2,3]

---

🅰️ (제출 답) ✅ (풀이 과정)

function flatten(arr){
    let newArr =[];
    
    function inner(arr) {
        for(let i=0; i<arr.length; i++){
            if(typeof arr[i] === 'object'){ //배열 타입은 object
                return inner([...arr[i], ...arr.slice(i+1)]);
            }
            newArr.push(arr[i]);
        }
    }
    inner(arr)    
    return newArr;
}

🤼‍♀️  다른 풀이 1 (강의 솔루션)

    function flatten(oldArr){
      var newArr = []
      	for(var i = 0; i < oldArr.length; i++){
        	if(Array.isArray(oldArr[i])){
          		newArr = newArr.concat(flatten(oldArr[i]))
        	} else {
          		newArr.push(oldArr[i])
        	}
      } 
      return newArr;
    }

=>

- Array.isArray(입력값) ? 배열이면 true, 아니면 false 반환.

- 내 풀이에서 concat을 적용하면, 아래와 같이 바꿀 수 있겠다. 

// return inner([...arr[i], ...arr.slice(i+1)]);
return inner(arr[i].concat(arr.slice(i+1)))

 

---

#Prac 19. capitalizeFirst

Write a recursive function called capitalizeFirst. Given an array of strings, capitalize the first letter of each string in the array.

// capitalizeFirst(['car','taco','banana']); // ['Car','Taco','Banana']

 

---

🅰️ (제출 답) ✅ (풀이 과정)

function capitalizeFirst (arr) {
  let newArr = [];
  for(let i =0; i< arr.length; i++){
      let first = arr[i][0].toUpperCase();
      newArr.push(first.concat(arr[i].slice(1)));
  }
    return newArr;
}

=> 재귀로는 어떻게..

 

🤼‍♀️  다른 풀이 1 (강의 솔루션)

function capitalizeFirst (array) {
      if (array.length === 1) {
        return [array[0][0].toUpperCase() + array[0].substr(1)];
      }
      const res = capitalizeFirst(array.slice(0, -1));
      const string = array.slice(array.length - 1)[0][0].toUpperCase() + array.slice(array.length-1)[0].substr(1);
      res.push(string);
      return res;
    }

---

#Prac 20. nestedEvenSum

Write a recursive function called nestedEvenSum. Return the sum of all even numbers in an object which may contain nested objects.

---

🅰️ (제출 답) ✅ (풀이 과정)

function nestedEvenSum (obj) {
    let result = 0;
    for(let key in obj){
        let check = obj[key];
        if(typeof check === 'number'){
            if(check % 2 ===0) {
            result += check;
            }
        } else if(typeof check === 'object') {
            result += nestedEvenSum(check);
        }
    }
    return result;
}

🤼‍♀️  다른 풀이 1 (강의 솔루션)

    function nestedEvenSum (obj, sum=0) {
        for (var key in obj) {
            if (typeof obj[key] === 'object'){
                sum += nestedEvenSum(obj[key]);
            } else if (typeof obj[key] === 'number' && obj[key] % 2 === 0){
                sum += obj[key];
            }
        }
        return sum;
    }

---

#Prac 21. capitalizeWords

Write a recursive function called capitalizeWords. Given an array of words, return a new array containing each word capitalized.

---

🅰️ (제출 답) ✅ (풀이 과정)

function capitalizeWords(arr) {
    if(arr.length === 1) {
        return [arr[0].toUpperCase()];
    }
    const res = capitalizeWords(arr.slice(0, -1));
    const string = arr.slice(arr.length-1)[0].toUpperCase();
    res.push(string);
    return res;
}

console.log(capitalizeWords(['car','taco','banana'])); //CAR,TACO,BANANA

🤼‍♀️  다른 풀이 1 (강의 솔루션)

    function capitalizeWords (array) {
      if (array.length === 1) {
        return [array[0].toUpperCase()];
      }
      let res = capitalizeWords(array.slice(0, -1));
      res.push(array.slice(array.length-1)[0].toUpperCase());
      return res;
    }

---

#Prac 22. stringifyNumbers

Write a function called stringifyNumbers which takes in an object and finds all of the values which are numbers and converts them to strings. Recursion would be a great way to solve this!

---

🅰️ (제출 답) ✅ (풀이 과정)

안 풀리는데 이유가 뭔지 모르다가!! 답과 조건 하나가 다르다는 것을 발견

!Array.isArray(obj[key]) // object이면서 배열이 아닌 경우 재귀함수 적용,,

🤼‍♀️  다른 풀이 1 (강의 솔루션)

    function stringifyNumbers(obj) {
      var newObj = {};
      for (var key in obj) {
        if (typeof obj[key] === 'number') {
          newObj[key] = obj[key].toString();
        } else if (typeof obj[key] === 'object' && !Array.isArray(obj[key])) {
          newObj[key] = stringifyNumbers(obj[key]);
        } else {
          newObj[key] = obj[key];
        }
      }
      return newObj;
    }

---

#Prac 23. collectStrings

Write a function called collectStrings which accepts an object and returns an array of all the values in the object that have a typeof string

const obj = {
    stuff: "foo",
    data: {
        val: {
            thing: {
                info: "bar",
                moreInfo: {
                    evenMoreInfo: {
                        weMadeIt: "baz"
                    }
                }
            }
        }
    }
}

collectStrings(obj) // ["foo", "bar", "baz"])

---

🅰️ (제출 답) ✅ (풀이 과정)

function collectStrings(obj, newArr = []) {
    for(let key in obj){
        if(typeof obj[key] === 'string'){
            newArr.push(obj[key]);
        } else if(typeof obj[key] === 'object' && !Array.isArray(obj[key])){
            collectStrings(obj[key], newArr);
        } 
    }
    return newArr;
}

🤼‍♀️  다른 풀이 1,2(강의 솔루션)

//Helper 메소드 재귀 버전
	function collectStrings(obj) {
        var stringsArr = [];
     
        function gatherStrings(o) {
            for(var key in o) {
                if(typeof o[key] === 'string') {
                    stringsArr.push(o[key]);
                }
                else if(typeof o[key] === 'object') {
                    return gatherStrings(o[key]);
                }
            }
        }
     
        gatherStrings(obj);
     
        return stringsArr;
    }
    
// 순수 재귀 버전
    function collectStrings(obj) {
        var stringsArr = [];
        for(var key in obj) {
            if(typeof obj[key] === 'string') {
                stringsArr.push(obj[key]);
            }
            else if(typeof obj[key] === 'object') {
                stringsArr = stringsArr.concat(collectStrings(obj[key]));
            }
        }
     
        return stringsArr;
    }