Fibonacci 수열

🌱 피보나치 수열(Fibonacci)

• 정의: 앞 두 수를 더해서 다음 수를 만드는 수열
  1, 1, 2, 3, 5, 8, 13, ...

 

• 일반 수식:
  fib(1) = 1 fib(2) = 1 fib(n) = fib(n-1) + fib(n-2) (n ≥ 3)

 

---

🔹 재귀 함수로 구현

1️⃣ 단순 재귀

 

public static int fib(int n) { if (n == 1 || n == 2)

// 1번째, 2번째 수는 1

return 1;

return fib(n - 1) + fib(n - 2); // 재귀 호출 }

• 장점: 코드가 간단하고 정의와 거의 동일
• 단점: n이 커지면 같은 계산을 반복 → 느려짐

    // 1️. 재귀 방식 피보나치

    public static int fib(int n) {

        if (n == 2 | n == 1) // fib(1) = 1, fib(2) = 1, 0번째 수는 포함 안함, 대부분 이렇게 처리

            return 1;

        result = fib(n - 1) + fib(n - 2);

        return result;

    }

 

 

재귀 함수의 구성요소

1) 종료 조건 (만약, 스택 오버플로우)

2) 함수 안에 함수.. 

 

🔹 디버깅 포인트

1. | 대신 || 사용
   • |는 비트 연산자, 조건문에서는 ||가 적절
2. 재귀 호출 시 return이 중요
   • return fib(n-1) + fib(n-2); → 결과가 계속 올라가도록 함
3. 매개변수로 값을 전달하려면 return으로 제대로 전달

 

---

 

• 각 세로 줄 = 콜 스택(Call Stack)
• 세로로 쌓이는 사각형 = 함수가 호출될 때 스택에 쌓인 상태
• 밑에 노란 동그라미 숫자 = 함수가 반환한 값(return value)

즉, 함수를 호출 → 스택에 쌓임 → base case 도달 → 값 반환 → 스택에서 제거 흐름을 시각화한 그림이다.

 

---

2️⃣ 예시: fib(5)

• 우리는 fib(5)를 구하려고 함
• 규칙: fib(n) = fib(n-1) + fib(n-2)
• base case: fib(1) = 1, fib(2) = 1

호출 순서

1. fib(5) 호출 → 스택에 fib(5) 쌓임
2. fib(4) 호출 → 스택에 fib(4) 쌓임
3. fib(3) 호출 → 스택에 fib(3) 쌓임
4. fib(2) 호출 → base case → 값 1 반환 (노란 동그라미 1)
5. fib(1) 호출 → base case → 값 1 반환 (노란 동그라미 1)
6. fib(3) 계산 완료 → 1 + 1 = 2 반환 (노란 동그라미 2)

이 과정에서 호출 → 깊게 들어가 → base case → 반환 → 스택에서 제거 순서가 반복됩니다.

 

 

 

3️⃣ 그림에서 번호 이해하기

• 그림 위쪽 스택: 함수가 호출되어 쌓인 상태
• 아래 노란 동그라미: 값이 부모 함수로 반환된 순간
• 예: 첫 번째 노란 1 → fib(2)가 1을 반환
• 그 다음 노란 2 → fib(3)이 fib(2)+fib(1)을 계산해서 2 반환

즉 “1을 준다” = 반환(return) 값이라고 보면 됩니다.

 

4️⃣ 그림을 보는 팁

1. 왼쪽에서 오른쪽 → 시간 순서대로 함수 호출/반환
2. 쌓인 스택 높이 → 현재 호출된 함수의 깊이
3. 동그라미 숫자 → 그 순간 스택 맨 위 함수가 계산한 값이 부모에게 올라가는 것
4. 같은 함수 여러 번 등장 → 단순 재귀에서는 중복 계산됨

 

 

---

실행 흐름과 재귀 구조의 차이

가장 먼저 이해해야 할 중요한 점은 컴퓨터의 실제 실행 흐름과 우리가 머릿속으로 그리는 재귀 호출 구조(트리 모양)는 다르다는 것입니다.

• 재귀 구조 (전체 지도): fib(5)를 계산하려면 fib(4)와 fib(3)이 필요하고, fib(4)를 계산하려면 fib(3)과 fib(2)가 필요한 것처럼, 문제의 전체 관계를 보여주는 큰 그림입니다.
• 실행 흐름 (탐험가의 발자취): 컴퓨터는 한 번에 한 가지 일만 할 수 있습니다. 따라서 이 큰 그림을 한 번에 보지 못하고, 하나의 길을 끝까지 파고드는 방식으로 움직입니다. 이것이 바로 그림의 ①~⑮ 순서입니다.

컴퓨터는 fib(5)를 만나면 왼쪽 길인 fib(4)를 먼저 탐험합니다. 그리고 fib(4) 안에서 또 왼쪽 길인 fib(3)으로 들어갑니다. 이렇게 가장 깊은 곳(fib(1))까지 탐험하고 나서야 되돌아와서 다음 길을 탐험합니다.

 

그림에서 “1을 준다” 라는 의미

 

그 그림에서 1은 함수의 반환값(return value) 를 표시한 겁니다.
fib(1) 또는 fib(2)가 기본 사례(base case)로서 1을 반환하니까, 그 노드/화살표에 1이라고 적혀있는 거예요.
즉 “값을 준다” = 그 호출이 1을 계산해서 돌려준다는 뜻입니다.

 

호출(방문) 순서 ≠ 실행(완료) 순서 — 다름

• 방문(호출) : “함수에 진입한 순간” — 보통 트리에서 노드를 처음 만나는 것(Preorder 느낌).
• 완료(반환) : “그 함수의 모든 하위 호출이 끝나고 결과를 내리는 순간” — 트리에서 자식들을 모두 처리한 뒤 노드가 결정되는 시점(Postorder 느낌).