🗃️ 알고리즘 | 재귀 함수(Recursion), 피보나치 수

algorithm

🗃️ 알고리즘 | 재귀 함수(Recursion), 피보나치 수

grasinnong 2020. 7. 23. 18:26

what is 재귀 함수

많은 사람들이 맛집에서 밥을 먹기 위해 줄을 섰다. 현재 나는 줄의 맨 끝에 위치하고 있다. 현재 내가 몇 번째로 대기하고 있는지 알고 싶다면 앞 사람에게 몇 번째인지 물어보면 된다. 만약 앞 사람이 모른다면 앞 사람은 자신의 앞 사람에게 물어보고 이 과정이 반복될 것이다(첫 번째 대기자까지).

나는 앞 사람에게 '저는 5번이에요' 라는 대답을 들었다. 그렇다면 나의 대기번호는 5 + 1 = 6번 이다.

그 과정을 코드를 작성하면 아래와 같다.

function getMyPositionInLine(person){
  if (person.nextInLine == null){
  //앞사람 존재 x
    return 1;
  }
  
  return 1 + getMyPositionInLine(person.nextInLine);
}

이렇게 함수 안에서 자기 자신(함수)을 다시 호출하는 함수를 재귀 함수라고 한다.

재귀 함수 구조

재귀 함수에서는 조건문이 중요하다. 조건문 안에는 재귀 함수의 종료 조건을 넣어주어야 한다.

why we use 재귀 함수

재귀 함수는 for 문과 while 문으로 대체가 가능하다.

function recursion(someValue){
  while(someValue < 10){
    someValue += 1;
  }
  
  return ;
}

하지만 아래와 같이 배열 안에 배열이 들어있고 똑같은 로직이 반복되는 경우에는 for 문이 계속 중첩될 수 있다.

function recursionArr(array){
  let sum = 0;
  for(let i = 0; i < array.length; i++){
  //만약 요소가 배열이라면 
    if (type of array[i] === 'array'){
      for (let j = 0; j < array[i].length; j++){
        //만약 요소가 배열이라면 
        if (type of array[i] === 'array'){
         //... 반복
        }
      }
    }
    else {
      sum += array[i];
    }
  }
  
  return sum;
}


recursionArr([1, [1,3, [1,2,4]]]);

재귀 함수를 사용할 경우, 코드를 더 직관적으로 간결하게 짤 수 있다.

function recursionArr(arr, sum){
  for (let i = 0; i < arr.length; i++){
    if (typeof arr[i] === 'number'){
      sum += array[i];
    } else {
      return recursionArr(array[i], sum);
    }
  }
  
  return sum;
}


recursionArr([1, [1,3, [1,2,4]]], 0);

Call Stack

콜 스택의 작동 과정은 다음과 같다.

function a(){
  return "hello " + b();
};

function b(){
  return "my " + c();
};


function c(){
  return "friends.";
};

1. call stack 에 "hello " + b() 작업이 들어간다.

2. 함수 a에서는 함수 b를 호출하고 있기 때문에 "my " + c() 작업이 들어간다.

3. 함수 b에서는 함수 c를 호출하고 있기 때문에 "friends ." 작업이 들어간다.

4. 작업들이 실행되면서 작업들이 call stack에서 pop된다(return).

재귀 함수에서 콜 스택은 다음과 같다.

function a(){
  return a();
}

종료 조건이 없을 경우 call stack에는 계속 함수 a()가 호출되어 쌓이게 된다. 콜 스택이 넘치게 되면 메모리 부족으로 에러가 발생한다(stack overflow!).

꼬리 재귀 최적화(Tail Recursion)

재귀 함수의 경우, 반복문에 비해 시간도 오래 걸리고, 스택이 넘치는 경우가 생긴다. 이러한 문제를 해결하기 위해 많은 언어들은 꼬리 재귀 최적화라는 기능을 제공한다.

꼬리 재귀 최적화는 선형 알고리즘을 만들어 실행하게 한다. 선형 알고리즘은 시간복잡도가 O(n)인 알고리즘이다. 때문에 코드가 계속 추가되더라도 최대 n번을 반복하게 된다.

피보나치 수(Fibonacci numbers)

피보나치 수는 F(0) = 0, F(1) = 1이고, n이 2 이상 일때는 F(n) = F(n-1) + F(n-2) 인 수열이다.

1, 1, 2, 3, 5, 8, ....

재귀 함수를 이용하여 n 번째 피보나치 수를 출력하는 함수를 만들어 보자.

1. Recursion

function fib(n){
let result = 0;
  if (n === 1 && n === 2){
    result = 1;
  } else if (n >= 2){
    result = fib(n-1) + fib(n-2);
  }
  return result;
};

5번째 피보나치 수를 구하는 경우는 별 문제가 없다고 하더라도, 만약 n이 100이면 fib함수가 아주 많이 call stack에 쌓이게 될 것이다.

피보나치 수를 구할 때 재귀 함수를 사용하는 경우, 시간복잡도는 O(2^n) 이 된다.

이외에도 피보나치 수열을 푸는 방법이 여러가지 있다.

2. Memoized solution(store)

fib(5) 값을 구할 때, fib(3)이 반복적으로 호출된다. store 방식은 처음 fib(3)가 호출되었을 때, 값을 기억한 다음 두번째 fib(3)을 구할 때 그 값을 사용한다.

function fib(n,memo){
  if(memo[n] !== null){
    return memo[n];
  } 
  
  if (n === 1 || n === 2){
    result = 1;
  } else {
    result = fib(n-1) + fib(n-2);
    memo[n] = (result);
  }
  return result;
}

f (1) = 1, f(2) = 1, f(3) = 2... 값들을 배열안에 넣었다.

[1, 1, 2, ...]

만약 다시 f(3) 값이 필요할 경우 memo에서 n번째 인덱스 값을 리턴하면 된다.

이 경우에는 시간복잡도가 최대 O(n)이 된다.

3. Bottom-up Approach

function fib(n){
  if (n === 1 || n === 2){
    return 1;
  } else {
  let array = [];
  array.push(1,1);
    for(let i = 2; i < n; i++){
      array.push(array[i-2] + array[i-1]);
    }
  }
  return array[array.length - 1];
}

fib(1) 부터 fib(n)까지의 값을 array에 저장시키는 방식이다. fib(1) 부터 fib(2)까지 채워넣고([1,1]), fib(3) 부터는 fib(3-1) + fib(3-2) 로 값을 n까지 구하는 방식이다.

이 경우 시간복잡도는 O(n)이다.

[참고자료]