[프로그래머스 강의] 4강 재귀함수

---

'어서와! 자료구조와 알고리즘은 처음이지?'

 

퇴근하고 싶다.....😂

---

 

재귀함수(Recursive function)

하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 것을 말한다. 

 

피보나치 순열(Fibonacci)

n = 0 → 0

n = 1 → 1

f(n) = f(n-1) + f(n-2)

 

[ 문1. 피보나치 순열을 재귀함수와 반복문으로 풀이하라 ]

# 재귀함수

def Fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fibonacci(n-1) +  Fibonacci(n-2) 
    
def solution(x):
    return Fibonacci(x)

 

# 반복문

def solution(x):
    answer = 0
    cur, next = 0,1 
    
    # x 가 1인 경우 
    if x == 1:
        return 1
    
    # x 가 2 이상인 경우 
    else:
        for n in range(x+1):
            if n >= 2:
                answer = cur + next 
                cur = next 
                next = answer 
    return answer