JavaScript 재귀함수

mh·2021년 12월 8일

JavaScript recursive 재귀함수 프론트엔드 함수

멋쟁이사자 프론트엔드 1기

목록 보기

11/12

재귀함수

재귀호출을 수행하는 함수

재귀호출(recursive call)
함수가 자기자신을 호출하는 것

재귀함수로 반복문 처리하기

재귀호출(함수안에서 함수 다시 불러오기)
종료조건(탈출조건) 체크 (없을시 무한재귀호출 -> Stack overflow Error)
반복문으로 구현할 수 있는 것은 재귀함수로 모두 구현가능
재귀함수로 구현 가능한 것은 반복문으로 대부분 구현(복잡도를 증가시키면) 가능

ex) 10~0 까지 출력하는 함수

for문을 이용한 함수

function countdown(n) {
 for (var i = n; i >= 0; i--) console.log(i);
}
countdown(10)

반복문 없이 만든 함수 (재귀함수)

function countdown(n) {
  if (n < 0) return;
  console.log(n);
  countdown(n - 1); //재귀호출
}

countdown(10);

ex2) 팩토리얼(계승) 만들기

팩토리얼(계승)
1부터 자기자신까지 모든 양의 정수의 곱
n! = n*(n-1)*(n-2)*...*3*2*1

function factorial(n) {
  //탈출 조건: n이 1 이하일 때 재귀 호출을 멈춘다.
  if (n <= 1) return 1;
  // 재귀 호출
  return n * factorial(n-1);
}

console.log(factorial(0));
console.log(factorial(1));
console.log(factorial(2));
console.log(factorial(3));
console.log(factorial(4));
console.log(factorial(5));

함수이름 -> 함수내부에서 유효 -> 함수내부에서 함수이름(자신) 사용 -> 자기자신 호출

함수표현식으로 정의한 함수 -> 식별자로도 재귀호출가능

var factorial = function foo(n) {
  if (n <= 1 ) return 1; //n이 1 이하일때 1리턴 (실행종료 후 값 1 반환)
  return n * factorial(n - 1);
  //함수를 가리키는 식별자로 자기자신 호출
};
console.log(factorial(5));

var factorial = function foo(n) {
  if (n <= 1 ) return 1;
  console.log(factorial === foo); //true 똑같다
  return n * foo(n - 1);
  //함수이름으로 자기자신 호출
};
console.log(factorial(5));

console.log(factorial === foo) 4번 실행 후 5번째 실행에서 반환return 1;으로 인해 실행 안됨 -> 리턴발생시 이후의 문은 무시한다, 함수는 return하면 휘발된다

ex3) sigma 만들기

\sum_{k=1}^N 2k

ex) k=1 N=3일 경우 1에서~3을 2k 에 대입한 모든 값들의 합 ( 2 + 4 + 6 = 12 )

$` \sum_{k=1}^N k `$ 일 경우

function sigma(n){
    if(n <= 1) {
        return n
    }
    return n + sigma(n-1)
}

ex4) 피보나치 수열 만들기

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