피보나치 수열(재귀O)

문제 설명

  => 피보나치 수열의 갯수를 입력받고, 합계, 전체 수열을 열거하시오

  => 피보나치 수열은 이전 값과 현재 값을 더한 결과가 다음 값이 되는 수열입니다.(첫수열 값은 1입니다)

    ex) 5번째 피보나치 수열을 구하시오

       1번째 : 1 / 2번째 : 0 + 1 = 1 / 3번째 : 1 + 1 = 2 / 4번째 : 1 + 2 = 3 / 5번째 : 2 + 3 = 5

       그러므로 5번째 피보나치 수열의 값은 5입니다.

 

코드 작성 방식

 1. 피보나치 수열 갯수를 입력받음

 2. 수열의 갯수만큼 반복되는 for문 작성

 3. 반복문 내에서 fibo 메소드 호출

 4. fibo의 매개변수가 0또는 1일 경우 해당 값을 반환

 5. 2이상일 경우 fibo(num-1) + fibo(num-2)를 반환

    -> num이 0또는 1이 될때까지 계속 자기 자신을 호출 

 6. 결과값 출력

 

 

소스코드

public class main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		System.out.print("피보나치 수열 갯수 지정 : ");
		int nTemp = sc.nextInt();
		int sum = 1;
		
		System.out.println("피보나치 수열 나열");
		for(int i=1; i<=nTemp; i+=1) {
			System.out.print(fibo(i) + " ");
			sum += fibo(i);
		}
		System.out.println();
		System.out.println("피보나치 수열 합계 : " + sum);
	}
	
	public static int fibo(int num) {
		if(num == 0 || num == 1)
			return num;
		else
			return fibo(num-1) + fibo(num-2);
	}
}

 

재귀함수

1. 장점

    => 코드가 간결해짐

    => 변수 사용 감소(메모리 감소 X - 함수를 종료시키지 않고 반복하여 호출하므로 메모리 소비량은 증가)

2. 단점

    => 메모리 사용량 증가

    => 반복문에 비해 속도가 느림(오버헤드 발생 증가)

    => 스택 오버플로우 상황이 발생할 수 있음