Tag: 함수

피보나치 수열, 자바스크립트 재귀로 함수 만들기(feat.메모이제이션)

메모이제이션을 사용한 피보나치 수열의 재귀 함수
피보나치(Fibonacci) 수는 이탈리아 수학자인 레오나르도 보나치(Leonardo Bonacci)에 의해 연구되어 알려진 것으로, 토끼가 새끼를 낳아 매달 증가하는 토끼의 수에 관해 계산하는 것으로 유명합니다.

0부터 시작하는 수를 순서대로 나열하면,

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181…….와 같이 수가 증가하는데요.

바로 앞(n-1)의 수와 그 바로 앞(n-2)의 수를 더하면 현재의 수(n)가 됩니다.

다음 그림은 네모칸 채우기로 한 면의 길이가 피보나치 수와 같이 증가를 보이는 것을 알 수 있습니다.

출처:https://en.wikipedia.org/wiki/Fibonacci_number

사각형이 1/4씩 회전하며 그리는 나선형은 황금 비율(1.618)에 수렴하여 과학적이며 예술적인 비율을 만들어 낸다고 합니다.

https://en.wikipedia.org/wiki/Fibonacci_number

그럼 이 피보나치 수열을 재귀를 사용해 자바스크립트 함수로 만들어 보겠습니다.

const fibonacci = (n) => {

  if ( n <= 1 ) {
    return n;
  }
  
  return fibonacci(n-1) + fibonacci(n-2);
}

위 함수는 피보나치 수열을 재귀적으로 수행하지만 계산 양이 늘어날 때마다 시간 복잡도는 가파르게 증가합니다.

이는 계산의 중복 문제 때문인데요.

예를 들어 fibonacci(10)을 실행하면 fibonacci(9), fibonacci(8), fibonacci(7)……. 순서로 실행을 하게 되는데요.

fibonacci(9)는 다시 fibonacci(8), fibonacci(7), fibonacci(6)…. 을 실행하게 됩니다.

결국 이미 한 계산을 하고 또 하고 또 하고… 합니다.

하지만 이미 수행한 계산 결과를 배열로 저장해두고 거기서 값을 꺼내쓰면 계산의 중복은 발생하지 않으므로 효율적이고 아름다운 함수가 됩니다.

이를 메모이제이션(Memoization)이라고 하는데요.

메모이제이션을 사용하는 자바스크립트 코드는 다음과 같습니다.

const fibo = (num, memo) => {

      memo = memo || {}

      if(memo[num]){
          return memo[num]
      }

      if(num<=1){
          return num;
      }

      return fibo(num-1, memo) + fibo(num-2, memo);

}

간단하면서도 효율적으로 피보나치를 계산하는 자바스크립트 함수를 사용할 수 있습니다.

쉽고 빠르게 커링(Currying) 기법 이해하기(feat.자바스크립트)

커링(Currying) 기법의 이해와 사용, 그리고 장단점

커링(Currying)은 카레와 같은 스펠링을 갖고 있지만 그 유명한 하스켈(Haskell)이라는 이름의 출처인 수학&논리학자 하스켈 브룩스 커리(Haskell Brooks Curry)의 성(Family Name)입니다.

커링은 하나 이상의 매개변수(Parameter)를 갖는 함수를 부분적으로 나누어 각각 단일 매개변수를 갖는 함수로 설정하는 기법입니다.

식으로 설명하면 다음과 같습니다.

func(a, b, c) -> f(a)(b)(c)

위 식을 코드로 변경하면 함수를 리턴하면서 다음 매개변수를 받아 또 함수를 리턴합니다.

//non-curried
function plusFunc(a, b, c){
  console.log(a + b + c);
}

plusFunc(1, 2, 3);   // 6

//curried
function plusFunc(a){
    return function(b){
       return function(c){
          console.log(a + b + c);
       }
    }
}

plusFunc(1)(2)(4);  // 7

논커리와 커리의 차이를 확인해 보겠습니다.

non-curried : 함수 실행 시 파라미터가 모자라도 문제 없이 실행이 가능함
👉 함수 정의 : func(a, b, c)
👉 함수 실행 : func(a)
👉 실행 결과 : func(a, undefined, undefined)

curried : 함수가 인수를 전부 받을 때까지 실행을 보류함.
👉 함수 정의 : func(a, b, c)
👉 함수 실행 : func(a)
👉 실행 결과 : func(a)상태에서 b 함수 입력 대기

위 특징에 따라 다음과 같이 사용할 수 있습니다.

function setAppell(appell){
    return function(name) {
       console.log(appell + name);   
    }
}

const setName = setAppell('Mr.');
setName('Right');  // Mr.Right
setAppell('Mr.')('Baker'); //Mr.Baker

//ES6 화살표 함수
const setAppell = appell => name => console.log(appell + name);

const setName = setAppell('Miss.');
setName('Dior');  // Miss.Dior

또한 다음과 같이 이벤트와 파라미터를 동시에 전달할 때도 유용합니다.

const setNumber = (num) => (event) => {
     console.log(event.target.id+':'+num);
}

<div onClick="setNumber(2)(event)" id='myNum'>
  click
</div>

// myNum:2

그럼 커링의 장점을 요약하면 무엇이 있을까요?

장점👍
– 재사용 가능
– 생산성 향상(코드 양 감소)
– 가독성 향상

그렇다면 커링의 단점은 무엇일까요?

단점👎
– 함수가 깊이 깊이 중첩되면 메모리를 과다하게 점유할 가능성이 있는 것과 같은 맥락에서 커링을 과용하면
메모리와 속도에 문제점 발생 가능성이 있음

커링의 수학적인 설명이 필요하신 분을 위한 링크


커링을 사용하지 않아도 원하는 기능을 대부분 구현할 수 있지만 재사용성이나 가독성에 따른 생산성 향상을 위해 커링을 사용하면 좋은 효과를 기대할 수 있습니다. 커링을 직접 구현하지 않더라도 커링의 개념과 사용법에 대해 알아두면 다른 사람의 코드를 읽거나 로직을 이해하는데 큰 도움이 될 것이라 생각합니다.