프로그래머스 강의_4

재귀 알고리즘

1. 재귀 알고리즘 (Recursive Algorithm)
   하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것

ex) 문제 : 1부터 n까지 모든 자연수의 합을 구하시오.

def sum(n) :
  if n < = 1:
      return n 
  else :
      return n + sum(n-1)

n의 조건을 설정해 주지않으면 마이너스 숫자가 계속 반복되기 때문에 재귀함수에서 종결 조건을 주는 것은 굉장히 중요하다.
==> if 조건을 통해 종결할 수 있도록 조건을 설정하는 것이 중요하다.

2. 재귀 알고리즘의 효율
   Iterative version

     deff sum(n) :
        s=0 
        while n>=0
          s+= n
          n-=1
        return s

 n이 커지면 n에 비례하는 만큼의 순환문 반복을 해야하기 때문에 복잡도는 O(n)으로 같다. 
 

3. 연습문제 - Fibonaci 순열
   <답안>
   
   위의 방법은 재귀함수를 이용
   아래의 방법은 반복문활용이다.