함수식 프로그래밍 학습 1 피보나치 수열 계산이 가져온 사고 변화

1229 단어

첫 번째 기법

def fib(n:Int):Int = {
  def loop(i:Int):Int = {
    i match {
      case 1 => 0
      case 2 => 1
      case _ => loop(i - 1) + loop(i - 2)
    }
    
  }
  loop(n)
}

일정한 프로그래밍 능력을 가진 사람을 믿는다. 이런 귀속 함수를 쓰는 것은 어렵지 않을 뿐만 아니라 사람의 사고방식과 가장 가깝다. 그러나 두 층의 귀속이 창고에 대한 소모는 완전히 지수급이다. 이것을 다 쓰고 나면 다음에 어떻게 최적화해야 하는지를 반드시 고려할 것이다.꼬리 귀속 최적화는 귀속을 위해 매우 자주 사용하는 최적화 방식이다. 그러면 문제가 생겼다. 상술한 코드에 대해 어떻게 꼬리 귀속을 할 수 있는 개조를 하는가.일반적인 방법도 생각하기 쉽다. 바로 귀속 방법에 중간 결과를 저장하는 것이다.그러면 다음 버전의 코드는 다음과 같습니다.
 

두 번째 기법

def fib2(n:Int):Int = {
  @annotation.tailrec
  def loop(n:Int,pre:Int,current:Int):Int={
    if(n == 1){
      pre
    } else {
      loop(n-1,current,current+pre)
    }
  }
  loop(n,0,1)
}

수조는 0, 1부터 시작하여 모두 N자리를 걷고 마지막에 1에 도착했을 때pre의 값이다. 
 

세 번째 기법

def fib3(n:Int):Int = {
  def loop(first:Int,second:Int):Stream[Int] = first #:: loop(second,first+second)
  
  loop(0,1).take(n).last
}

 
이것은 scala에서 매우 전형적인stream을 사용한 것이다. 그러면 일반인의 사고방식과 일치할 뿐만 아니라 창고 의존이 너무 많은 문제를 피할 수 있다. 
 
 

총결산


전체적인 감각이 아직 제자리에 맞지 않으니 후속적으로 사고가 더욱 뚜렷해지면 다시 보충해 봅시다. 

좋은 웹페이지 즐겨찾기