TIL : 재귀(Recursion) 함수 / fibonacci numbers 구현

TIL : 재귀(Recursion) 함수 / fibonacci numbers 구현

인피니트 반복, 은 에러;; / picture by 캡틴.

 

오늘은 재귀 함수를 활용한 피보나치수열(fibonacci numbers) 구현을 공부하였다.

 

재귀 함수란, 자기 자신을 호출하는 함수를 의미한다.

함수에 숫자가 주어지면 1씩 작은 숫자를 곱하고, 마지막으로 1을 곱하여

그 결과를 반환하는 로직에 재귀 함수가 사용되는 예시를 강의에서 보게 되었다.

 

 

function multiply(n){
  if(n === 1){
    return 1;    // 1은 더이상 곱할 숫자가 없기때문에, 1을 반환
  }
  return n*multiply(n-1); // multiply( )함수를 함수 안에서 다시 사용(= 재귀함수)
}

// multiply(5) -> 5*multiply(4) 5*[4*{3*(2*1)}] = 120
// multiply(4) -> 4*multiply(3) 4*{3*(2*1)}
// multiply(3) -> 3*multiply(2) 3*(2*1)
// multiply(2) -> 2*multiply(1) 2*1

---

multiply( ) 함수 예시를 통해 알게 된 재귀 함수의 개념을 가지고,

본격적으로 피보나치 수열(fibonacci numbers)을 반환할 수 있는 함수를 구현해 보았다.

 

 

 

피보나치수열(Fibonacci numbers)

첫째 및 둘째 항의 값이 1이며, 그 뒤에 나열되는 모든 항은 바로 앞 두 항의 합계를 값으로 하는 수열. 

     예) 1, 1, 2, 3, 5, 8, 13 ...

 

이 수열을 재귀 함수를 사용하여 구현하기 위해서는, '규칙'을 발견하는 것이 중요하다고 생각했다.

앞서 정의한 내용 중에 바뀌어서는 안 되는 내용(고정값)과, '규칙' 발견을 위해 연속하여 몇 개 항과

그 항에 할당되는 값을 풀어서 적어보았다.

 

---

f(1) = 1
f(2) = 1

여기까지가 절대적으로 나와야 하는 값.

f(3) 부터는, '규칙'으로 볼 수 있는(= 재귀 함수를 적용할 수 있는) 모양을 발견했다.

f(3) = f(2) +f(1) = 1 + 1 = 2

f(4) = f(3) + f(2) = 2 + 1 = 3

f(5) = f(4) + f(3) = 3 + 2 = 5

f(6) = f(5) + f(4) = 5 + 3 = 8

 

  * f(n) = f(n-1) + f(n-2) 를 재귀 함수로서 함수를 실행할 때마다 반복하여 호출되도록 구현하기로 했다.

 

 

 

function fiboNum(n){
  if (n<3){
    return 1;       // 1, 2번째 항은 무조건 1을 갖는 절대조건 설정.
  }else if(3<=n){
    result = fiboNum(n-1) + fiboNum(n-2); // 3 이상의 항에 대해서는 이전 두 항의 합 계산.
  }
  return result;
}


function fiboNum(n){
  if (n<3){
    return 1;       // 1, 2번째 항은 무조건 1을 갖는 절대조건 설정.
  }else{            // 첫 번째 if문 조건 외의 모든 것을 대상으로 하는, 간단한 코드로도 바꿀수가 있었다.
    result = fiboNum(n-1) + fiboNum(n-2);
  }
  return result;
}

 

 

---

 

이제, 마지막 과제인 recursion을 남기고 있다.

아직 pair programming도 1~2번 더 남았고, 코플릿 문제도 몇 개 완료하다 남은 항목이 있다.

 

한 주 동안 recursion 풀이에 정신이 없겠지만,

처음 배운 배열 메소드나 객체를 다루는 javascript도 한번 더 찬찬히 들여다볼 수 있는 여유가 생겼으면 좋겠다.

(아마 없겠지만;)