재귀함수 :: 피보나치 수열 알고리즘

재귀함수 Recursive Function

 

@사진을 사실 넣으려고 했는데, 개인적으로 싫어하는 형태라 사진을 생략하겠다.

@엘레베이터 거울을 보면 속에 여러개 보이는 형태가 재귀함수의 이미지와 같다.

 

재귀함수에서 재귀(再歸, Recursion)는 '다시 자신에게 돌아간다'라는 의미다.

즉, 함수가 자신을 다시 호출해서 반복하는 형태의 함수를 재귀함수라고 한다.

 

때문에 재귀함수에서는 탈출조건을 반드시 마련해줘야만 무한루프를 막을 수 있다.

 

가장 많이 사용되는 예제는 일명 팩토리얼(계승, !, Factorial) 구현이 있다.

 

---

~ 광고 타임 ~

---

 

JAVA 재귀함수 예제

package tisory.blog.it_ing;

public class Main {
	
	public static void main(String[] args) {
		System.out.print("# 아이티-잉 계승\n5! = ");
		int number = fn_factorial(5);
		System.out.print(" = " + number);
	}
	
	public static int fn_factorial(int n){
		System.out.print(n);
		if(n <= 1){ //탈출 조건
			return 1;
		}else{
			System.out.print(" X ");
			return n * fn_factorial(n-1);	// 재귀적 호출
		}
	}
}

 

 

출력

 

 

 

단계적으로 보면, 총 5차례 실행이 된다.

즉, 총 5차례 호출되고, 5 x (5-1) x (5-1-1) x (5-1-1-1) x (5-1-1-1-1) x 1 과 같다.

 

 

 

 

 

---

~ 광고 타임 ~

---

 

 

 

 

피보나치 수열 Fibonacci Sequence

 

 

아마 중학교 때 배웠던 것 같은데 대표적인 수열 중 하나다.

만약 첫번째 원소 A와 두번째 원소 B가 있을 때, 세번째 원소 C는 A+B로 이루어지는 형태를 말한다.

 

이를 점화식으로 나타내면 다음과 같다.

 

 

 

 

수학적으로 접근하면 이 식을 통해 다양한 변형을 이끌어 낼 수 있지만,

우리는 알고리즘만 파악하면 되므로 생략하겠다.

 

 

예를 들어보면 다음과 같은 수열이 해당한다.

 

 

 

 

 

 

JAVA 코드

package tisory.blog.it_ing;

public class Main {
	static int cnt = 0;
	
	public static void main(String[] args) {
		int number = fn_Fibonacci(10);
		
		System.out.println("#아이티-잉 피보나치\nf(10)일 때, 함수 호출 횟수 : " + cnt);
	}
	
	public static int fn_Fibonacci(int n){
		cnt++;
		if(n == 0){
			return 0;
		}else if(n <= 2){
			return 1;
		}else{
			return fn_Fibonacci(n-1) + fn_Fibonacci(n-2);	
		}
	}
}

 

결과

 

 

 

구현은 어렵지 않지만, 이 글을 포스팅한 이유는 바로 여기에 있다.

 

피보나치 수열 10번째 항까지 구할 경우, 사람은 0, 1, 1, 2, 3, … 쭉쭉 총 10번의 연산으로 구할 수 있다.

하지만 재귀적 호출로 구현할 경우 위와 같이 177회 호출이라는 비효율적 현상이 발생한다.

 

 

그래서! 다음 시간에는 동적 프로그래밍(Dynamic Programming), 일명 디피(DP)를 살펴보고,

피보나치 수열 알고리즘을 재구현 해보도록 하겠다.

 

포스팅을 완료했으니, 동적계획법에 대한 정보는 링크를 통해 확인하자.

 

 

끝.