[#CodeUp] 1915 : (재귀함수) 피보나치 수열

https://codeup.kr/problem.php?id=1915

(재귀함수) 피보나치 수열

문제

---

피보나치 수열이란 앞의 두 수를 더하여 나오는 수열이다.

첫 번째 수와 두 번째 수는 모두 1이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다. 피보나치 수열을 나열해 보면 다음과 같다.

 

1, 1, 2, 3, 5, 8, 13 …

 

자연수 N을 입력받아 N번째 피보나치 수를 출력하는 프로그램을 작성하시오.

※ 이 문제는 반드시 재귀함수를 이용하여 작성 해야한다.

 

풀이

---

배열을 사용해서 각 단계에 맞는 값들을 저장해서 이용

import java.util.*;
public class Main {
    static void setArr(int[] arr, int i, int num){
        if(i == num) return;
        if(i<2) arr[i] = 1;
        else arr[i] = arr[i-1] + arr[i-2];
        i = i+1;
        setArr(arr, i, num);
    }
    public static void main(String[] arg) throws Exception{
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] arr = new int[num];
        int i = 0;
        setArr(arr, i, num);
        System.out.println(arr[num-1]);
    }
}

https://github.com/dopal2/CodeUp/blob/main/src/Main.java_1915