←
C · 재귀·연습 문제

재귀 피보나치

문제 설명PROBLEM

재귀 피보나치

문제

재귀 호출로 0, 1, 1, 2, ... 피보나치 수열의 n번째 값을 계산하세요.

구현할 함수

long long fibonacci(int n)

입력

0 이상 40 이하의 정수 n이 주어집니다.

입력 파싱과 결과 출력은 숨겨진 I/O 어댑터가 자동으로 처리합니다. 에디터에는 요구된 함수 또는 메서드 구현만 작성하세요.

출력

n번째 피보나치 수를 출력합니다.

구현 조건

  • 계산 로직은 반드시 fibonacci 함수 안에 구현하세요.
  • n < 2를 종료 조건으로 두고 n-1, n-2를 재귀 호출하세요.

공개 테스트

아래 테스트를 각각 독립된 프로세스로 실행합니다. 입력과 기대 출력은 실제 채점 순서와 같습니다.

#이름InputExpected output
10번째00
2대표713
310번째1055
개념 노트와 실수 포인트

재귀

  • 종료 조건(base case) + 자기 호출(recursive case) 두 부분이 핵심. 종료 조건이 없으면 무한 재귀.
  • 대표 패턴: 팩토리얼 n*f(n-1), 피보나치 f(n-1)+f(n-2), 최대공약수 gcd(b, a%b).
  • 추적은 가장 안쪽(종료)부터 거꾸로 계산.