[BOJ 10870] 피보나치 수 5

09 Feb 2026

Reading time ~4 minutes

문제 요약

피보나치 수열은

F(0)=0, F(1)=1
F(n)=F(n-1)+F(n-2) (n≥2)

이며, n(0 ≤ n ≤ 20)이 주어졌을 때 F(n) 을 출력한다.

내가 처음 작성한 코드 (print가 기대대로 안 됐던 버전)

import sys

input = sys.stdin.readline

n = int(input())

def pibo(num_before, num_now, n, count):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    num_new = num_before + num_now

    if count + 1 == n:
        return num_new
    else:
        pibo(num_now, num_new, n, count + 1)

print(pibo(0, 1, n, 1), end='')

왜 제대로 동작하지 않았나?

핵심은 재귀 호출 결과를 return으로 위로 전달하지 않았다는 점이다.

else:에서 pibo(...)를 호출만 하고 return을 안 했기 때문에,
그 분기에서는 함수가 None을 반환한다.
그래서 최상위 print(pibo(...))가 None을 출력하거나(또는 원하는 값이 나오지 않거나) 문제가 생긴다.

올바른 형태는 아래처럼 재귀 호출 앞에 return을 붙여야 한다.

return pibo(num_now, num_new, n, count + 1)

수정한 코드 (출력까지 재귀 안에서 처리)

import sys

input = sys.stdin.readline

n = int(input())

def pibo(num_before, num_now, n, count):
    if n == 0:
        print(0, end='')
        return 0
    elif n == 1:
        print(1, end='')
        return 0
    num_new = num_before + num_now
    if count + 1 == n:
        print(num_new, end='')
    else:
        pibo(num_now, num_new, n, count + 1)

pibo(0, 1, n, 1)

이 코드는 동작하지만,

함수가 “값을 반환”하기보다 “출력”을 직접 해버려서,
재사용/테스트 관점에서는 조금 불편할 수 있다.

개선된 코드 1 (추천): 지금 구조 유지 + return 제대로 하기 (tail recursion 스타일)

import sys
input = sys.stdin.readline

n = int(input())

def pibo(prev, curr, n, count):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if count == n:        # count가 n이면 curr이 F(n)
        return curr
    return pibo(curr, prev + curr, n, count + 1)

print(pibo(0, 1, n, 1))

이 코드에서 배울 수 있는 점

재귀는 “마지막에 얻은 값”을 반드시 return으로 위로 전달해야 한다.
출력(print)과 계산(return)을 분리하면 함수가 더 깔끔해진다.
tail recursion(꼬리 재귀) 형태로도 구현 가능하지만, 파이썬은 tail call 최적화가 없어서 n이 큰 문제에는 부적합할 수 있다(이 문제는 n≤20이라 OK).

개선된 코드 2 (대안): 가장 기본적인 재귀 정의 그대로 쓰기

import sys
input = sys.stdin.readline

n = int(input())

def fib(k):
    if k <= 1:
        return k
    return fib(k - 1) + fib(k - 2)

print(fib(n))

이 코드에서 배울 수 있는 점

수학적 정의를 그대로 코드로 옮긴 가장 직관적인 재귀 형태다.
다만 이 방식은 중복 호출이 많아 n이 커지면 느려지므로(지수 시간), 큰 n에서는 DP/메모이제이션/반복문이 필요하다.
이 문제는 n≤20이라 충분히 통과한다.

이번 문제로 배운 점 정리

sys.stdin.readline()은 빠른 입력 패턴으로 습관화해두면 좋다.
재귀 함수는 “재귀 호출 결과를 return으로 전달”하지 않으면 위로 값이 올라오지 않는다.
출력은 가능하면 마지막에 한 번만 하고, 함수는 값을 return하도록 만들면 재사용성이 좋아진다.