본문 바로가기

Python_Intermediate/Algorithmus

Python - 피보나치 수열(for문 / 재귀함수)

1. for문

def fib(n):
    list = []
    for i in range(0, n):
        if i < 2:
            list.append(1)
        else:
            list.append(list[i-1] + list[i-2])
    return list[n-1]

n = int(input())
print(fib(n))

- 값을 저장 하기 위한 빈 리스트 생성

- for문을 통해 배열의 인덱스는 0 부터 시작이므로 0 ~ n 까지 실행

- n의 값이 3보다 작으면 값이 1이므로 if < 2는 1를 추가

- 바로 앞의 두 피보나치의 수의 합을 구하여 되므로  else 구문

- 0부터 시작했으므로 list[n-1]

 

< http://pythontutor.com >

 

2. 재귀함수

def fib2(n):
    if n < 3:
        return 1
    else:
        return fib2(n-1) + fib2(n-2)

n = int(input())
print(fib2(n))

- 끝나는 구문을 반드시 지정 if n < 3 (n이 3보다 작으면 값이 1)

< http://pythontutor.com >