재귀함수 recursion Function

재귀 함수
함수가 직접 또는 간접적으로 자신을 호출하는 함수

필수 조건
재귀 함수는 끝나는 지점(종단점)을 설정해주어야 하고, 매번 다른 인풋 값이 들어갈 수 있도록 해야 함

주의할 점
종단점 미설정(무한 루프에 빠짐)
잘못된 값을 반환, 반환을 하지 않음(같은 인풋 값이 들어가서 무한루프에 빠짐)

 

 

// n부터 카운트다운 하는 함수

function consoleN(n) {
  if (n === 0) {   // 끝내는 조건
    console.log("done!");
    return;
  }
  console.log(n);
  n--;   // 매번 다른 인풋값
  consoleN(n);   // 자기자신 다시 호출
}

consoleN(3);

/*
3
2
1
done!
*/

// n까지 숫자의 합

function sumN(n) {
  if (n === 1) return 1;   // 종단점 설정
  return n + sumN(n - 1);   // 다른 인풋값으로 자기자신 호출
}

console.log(sumN(3));   // 6
console.log(sumN(4));   // 10

// n까지 숫자의 곱

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

console.log(factorial(3));   // 6
console.log(factorial(5));   // 120

 

 

helper 메서드 재귀
재귀적이지 않은 외부 함수가 재귀적인 내부 함수를 호출하는 패턴
일종의 결과를 컴파일할 때 흔히 사용되는 패턴
결과는 보통 배열 같은 데이터 구조

재귀 시 result가 재할당 되는 것을 방지하기 위해서
1. 스코프 밖에서 result 정의 후 재귀 함수를 사용하는 방법,
2. 함수 안에 재귀 함수를 정의하여 result 값을 찾아가는 방법

 

Ex) 배열에서 홀수 값을 찾아 새로운 배열로 출력

// 올바르지 않은 재귀함수 사용

function odd(arr) {
  let result = [];   // 재귀함수안에서 result 정의시 매번 []로 할당되는 문제 발생
  if (arr.length === 0) return;
  if (arr[0] % 2 !== 0) {
    result.push(arr[0]);
  }
  console.log(result);
  odd(arr.slice(1));
  return result
}

odd([1, 2, 3, 4, 5, 6]);

/*
[ 1 ]
[]
[ 3 ]
[]
[ 5 ]
[]
*/

console.log(result)   // [1]

// 재귀함수 밖에서 result 정의

let result = [];   // 스코프 밖에서 result 정의
function odd(arr) {
  if (arr.length === 0) return;
  if (arr[0] % 2 !== 0) result.push(arr[0]);
  console.log(result);
  odd(arr.slice(1));
}

odd([1, 2, 3, 4, 5, 6]);

/*
[ 1 ]
[ 1 ]
[ 1, 3 ]
[ 1, 3 ]
[ 1, 3, 5 ]
[ 1, 3, 5 ]
*/

console.log(result)   // [ 1, 3, 5 ]

// 함수안에 result를 정의한다면 내부에 재귀함수를 정의(helper 메소드 재귀)

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

  // 내부에 재귀 함수를 정의하고 호출함
  function helper(arr) {
    if (arr.length === 0) return;
    if (arr[0] % 2 !== 0) {
      result.push(arr[0]);
    }
    helper(arr.slice(1));
  }

  helper(arr);
  console.log(result);
  return result;
}

odd([1, 2, 3, 4, 5, 6]);   

// [ 1, 3, 5 ]