재귀함수

[MDN : Recursion]

Recursive Functions

• 정의 단계에서 자신을 재참조하는 함수를 뜻한다.
  (함수 내부에서 자기 자신을 호출하는 함수이다.)

• 조건이 충족될 때까지 자신을 호출한다.
  반복문을 돌리듯이 끊임없이 자신을 호출하다가 특정 조건이 되면 빠져나온다.

• 반드시 함수를 종료하는 조건을 만들어줘야 한다!

• 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다.

• 더 작은 하위 문제를 포함하는 문제를 해결하는 데 사용한다.
  재귀함수가 리턴하는 값에 추가적인 작업을 더 해야할 경우 사용하면 유용하다.

mdn에 나와있는 일반적인 사용 예시

/* 팩토리얼 */
const factorial = (n) => {
  if (n === 0) return 1;
  else return n * factorial(n - 1);
};
console.log(factorial(10));
// 3628800

/* 피보나치 수 */
const fibonacci = (n) => (n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2));
console.log(fibonacci(10));
// 55

/* reduce */
const reduce = (fn, acc, [cur, ...rest]) => (
  cur === undefined ? acc : reduce(fn, fn(acc, cur), rest)
);
console.log(reduce((a, b) => a + b, 0, [1, 2, 3, 4, 5, 6, 7, 8, 9]));
// 45

연습문제 풀이

/* count 수만큼 sum에 2를 더하는 함수 */
function WhatIsRecursion_02(count) {
    let sum = 0;

    function recursion(count, sum) {
        if(count <= 0) return sum

        sum += 2;
        return recursion(count-1, sum)
    }

    return recursion(count, sum)
}

/* 문자열 7을 제외한 나머지 문자들을 앞에서부터 제거한 후, 
    문자열 7을 찾았을 때에 제거한 문자열의 수를 리턴 */
function thisIsSeven(str) {
    function recursion(count) {
        if(str[0] === '7') return count

        str = str.substring(1, str.length)
        return recursion(count+1)
    }

    return recursion(0)
}

/*  문자열 7을 제외한 나머지 문자열들을 모두 제거한 후
    문자열 7만 문자열에 남겼을 때에 제거된 모든 문자열의 수를 리턴 */
function thisIsOnlySeven(str) {
    function recursion(count) {
        if(str.length === 1) return count

        if(str[0] !== '7') {
            str = str.substring(1, str.length)
            return recursion(count+1)
        } else if(str[str.length] !== '7') {
            str = str.substring(0, str.length-1)
            return recursion(count+1)
        }
    }

    return recursion(0)
}