[알고리즘] 재귀함수

1. 재귀함수

(1) 재귀함수란?

 - 재귀함수란 자기자신을 호출하는 함수이다.

(2) 재귀의 기본요소

 - 종료조건

 - 매번 다른 입력값

(3) 재귀의 위험요소

 - 종료조건이 없는경우 : 계속 반복

 - return을 하지 않은 경우

 - 스택 오버플로우 : 재귀호출이 멈추지 않는 경우

2. 콜스택 예시

function takeShower() {
  return "Showering!";
}

function eatBreakfast() {
  let meal = cookFood();
  return `Eating ${meal}`;
}

function cookFood() {
  let items = ["Oatmeal", "Eggs", "Protein Shake"];
  return items[Math.floor(Math.random() * items.length)];
}
function wakeUp() {
  takeShower();
  eatBreakfast();
}

wakeUp();

콜백 형식으로 함수들을 사용한다.

3. 재귀 예시

(1) 1씩 뺀값을 나타내기

 - for문 활용

function countDown(num){
    for(var i = num; i > 0; i--){
        console.log(i);
    }
    console.log("All done!")
}

 - 재귀 활용

function countDown(num){
    if(num <= 0) {
        console.log("All done!");
        return;
    }
    console.log(num);
    num--;
    countDown(num);
}

(2) 0부터 받은 파라미터까지 순서대로 모든 숫자의 합 구하기

function sumRange(num){
   if(num === 1) return 1; 
   return num + sumRange(num-1);
}

(3) 팩토리얼 구현

- for문 활용

function factorial(num){
    let total = 1;
    for(let i = num; i > 1; i--){
        total *= i
    }
    return total;
}

- 재귀 활용

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

(4) 받은 배열에서 홀수만 더하기

 - helper(다른함수)를 사용하여 함수안에서 helper 함수로 재귀함수를 구현했다.

function collectOddValues(arr) {
  let result = [];

  function helper(helperInput) {
    if (helperInput.length === 0) {
      return;
    }

    if (helperInput[0] % 2 !== 0) {
      result.push(helperInput[0]);
    }

    helper(helperInput.slice(1));
  }

  helper(arr);

  return result;
}

- 일반 재귀

function collectOddValues(arr){
    let newArr = [];
    
    if(arr.length === 0) {
        return newArr;
    }
        
    if(arr[0] % 2 !== 0){
        newArr.push(arr[0]);
    }
        
    newArr = newArr.concat(collectOddValues(arr.slice(1)));
    return newArr;
}

(5) 배열안의 값들을 모두 곱하기

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

(6) 피보나치

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