피보나치 수열을 만드는 n가지 방법 ㅡ 재귀함수, 제너레이터, yield, next, stack 자료구조

피보나치 수열을 만드는 여러 가지 코드를 짜 보고, 그 과정에서 재귀함수, 제너레이터에 대해 배웠다.

 

우선 아래는 풀이 시간 전에 직접 코드를 짜 본 내용으로, length를 넣으면 해당 수만큼 while문이 돌도록 작성했다.

리스트에 미리 1, 1 까지는 넣어두었던 점, 다른 코드보다 성능(연산 처리 속도)이 좋지 않다는 점이 아쉬웠다. 

# 피보나치 수열
# 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
fibo_list = [1, 1]

def fibo(length):
    while len(fibo_list) < length :
        a = fibo_list[-2] + fibo_list[-1]
        fibo_list.append(a)
        print(a)
    # a = 1
    # b = a
    # print (a+b)

 

 

1. for문

def fibo2(n):
    if n < 2:
        return n
    a, b = 0, 1
    for i in range(n):
        a, b = b, a+b
    return a

 

n번째 피보나치 수열을 구할 수 있도록 작성되었다.

내가 작성한 while문 보다는 빠르지만, 아래 소개될 코드들 보다는 느렸다.

이해하기에는 가장 직관적이고 쉽게 쓰여진 코드였다.

 

 

2. 재귀함수 

# 재귀함수 : 자기 자신을 호출하는 함수
def fibo_recu(n):
    if n < 2 : return n
    return fibo_recu(n-1) + fibo_recu(n-2)

 

재귀함수의 개념에 대해 배우면서 stack 이라는 자료구조에 대해서도 배웠다.

 

- 재귀함수는 함수 실행의 결과값을 stack에 insert 한다. (넣는다)  
- 실행이 완료되면 그 결과 값을 pop 한다. (꺼낸다)

 

# stack 자료구조 
- 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조 
- first in, last out <> Last in, first out 

- 통에 먼저 들어간 게 가장 마지막에 나온다. (머신러닝 데이터) 

 

 

3. 제너레이터

# 제너레이터 
# return은 함수가 return을 만나면 끝남
# yield 는 끝나지 않고 '잠시 대기' 상태가 됨
# yield 는 대기 상태에 있다가, next 명령어를 만나면 다시 작동함

def fib_generator():
    a, b = 0, 1
    while True:
        yield b
        a, b = b, a+b
        
fg = fib_generator()

for _ in range(10):
    print(next(fg))
    
# next(fg)

 

제너레이터는 메모리에 올리지 않고 사용할 만큼만 갖고 왔다가 next로 다음 내용을 가져온다.

지금까지 배운 함수 중에서 다음 구문들이 제너레이터 방식으로 작동하는 예시이다.

- with 구문 
- os_walk 구문 

os_walk 예시