intro : 재귀함수는 싫다. 싫어.

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

문제 풀이 (100ms)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입출력을 위한 BufferedReader 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 입력값을 받아서 정수로 변환
        int n = Integer.parseInt(br.readLine());
        // 재귀함수를 호출하고 return 받음
        int result = recursion(n);
        // 결과값 출력
        System.out.println(result);
        // 자원 반납
        br.close();
    }
    // 피보나치 계산을 수행할 재귀함수 
    public static int recursion(int n) {
        // 0과 1은 각자 자기자신의 값을 반환함
        if (n <= 1) {
            return n;
        }
        // recursion(10) = recursion(9) + recursion(8) ... 1까지 반복됨
        return recursion(n - 1) + recursion(n - 2);
    }
}

문제 해석

재귀함수의 기초를 닦을수 있는 문제인거 같다. 난 재귀함수 문제는 반복문으로도 풀수 있어야 한다고 생각해서 아래와같이 재귀함수로도 풀어보고 반복문으로도 풀어봤다. 두개의 풀이방식에는 차이가 있지만 결국에 구하고자하는 결과값은 피보나치 수열의 값을 어떻게 계산할 것인가? 가 포인트가 되는거 같다. 피보나치 수열에서의 중요한 점은 다음과 같은 단계로 나누어 볼 수 있다.

// 각 단계에서 메서드가 종료된게 아님, 
// return 문에서 새로운 recursion을 호출할때마다 해당 메서드 결과값 반환을 기다리고 있음
recursion(10) 호출 → recursion(9) + recursion(8) 계산을 기다림
recursion(9) 호출 → recursion(8) + recursion(7) 계산을 기다림
recursion(8) 호출 → recursion(7) + recursion(6) 계산을 기다림
recursion(7) 호출 → recursion(6) + recursion(5) 계산을 기다림
recursion(6) 호출 → recursion(5) + recursion(4) 계산을 기다림
recursion(5) 호출 → recursion(4) + recursion(3) 계산을 기다림
recursion(4) 호출 → recursion(3) + recursion(2) 계산을 기다림
recursion(3) 호출 → recursion(2) + recursion(1) 계산을 기다림
recursion(2) 호출 → 반환: 1 + 0 = 1
recursion(3) 반환 → 1 (recursion(2)) + 1 (recursion(1)) = 2
recursion(4) 반환 → 2 (recursion(3)) + 1 (recursion(2)) = 3
recursion(5) 반환 → 3 (recursion(4)) + 2 (recursion(3)) = 5
recursion(6) 반환 → 5 (recursion(5)) + 3 (recursion(4)) = 8
recursion(7) 반환 → 8 (recursion(6)) + 5 (recursion(5)) = 13
recursion(8) 반환 → 13 (recursion(7)) + 8 (recursion(6)) = 21
recursion(9) 반환 → 21 (recursion(8)) + 13 (recursion(7)) = 34
recursion(10) 반환 → 34 (recursion(9)) + 21 (recursion(8)) = 55

// 각 단계에서 값을 반환하고 차례대로 계산 진행
최종적으로 recursion(10)이 55을 반환

위 단계를 천천히 읽어보면 재귀함수의 호출 시점과 종료 시점에 대해서 알 수 있다.

반복문을 통해 재귀함수 없이 풀이 방법 - 106ms 소요

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        // 입력값을 받아서 정수로 변환
        int input = Integer.parseInt(br.readLine());
        // 배열의 크기를 21로 초기화
        int[] array = new int[21];
        // 인덱스 0번과 1번은 0과 1로 초기화
        array[0] = 0;
        array[1] = 1;
        // 반복문을 통해 피보나치 수열의 각각의 값을 계산
        for (int i = 2; i < array.length; i++) {
            array[i] = array[i - 1] + array[i - 2];
        }

        // 입력값으로 받은 찾고자 하는 값에 해당하는 값 append()
        sb.append(array[input]);
        // bw로 출력하기 위해 문자열로 변환 후 write
        bw.write(sb.toString());
        bw.flush();
        // 자원 반납
        bw.close();
        br.close();
    }
}

마무리

호출 단계와 메서드 종료 시점을 확인해보니 각 해당 단계에서 중복된 계산 결과가 반복 되는것을 확인 할 수 있었다. (recursion(8)이 recursion(10)와 recursion(9) 에서 각각 한번씩 총 두번 호출 됨) 재귀함수에서는 각 계층에서의 호출이 각각 일어나기에 추적하기 어려웠던 부분인데, 그림으로 그려보고 눈으로 확인해보니 확실하게 알 수 있었던 것 같다. 다음에는 좀 더 최적화된 로직 구현 방법을 적용해 보고 싶다.

I am visible

contact

문제

입력

출력

문제 풀이 (100ms)

문제 해석

반복문을 통해 재귀함수 없이 풀이 방법 - 106ms 소요

마무리