기초 수학 - 4. 점화식과 재귀함수

점화식 (Recurrence)

어떤 수열의 각각의 항들이 어떤 관계를 가지고 있는지를 나타낸 식을 의미합니다.

 

보통 점화식은 n번째의 항을 이전의 항들을 이용하여 정의하게 됩니다.

 

피보나치 수열이 대표적인 예입니다.

피보나치 수열

 

재귀함수 (Recursion)

어떤 함수가 자기 자신을 다시 호출하여 작업을 수행하는 방식을 뜻합니다.

 

재귀함수는 자기 자신을 호출하기 때문에 영원히 반복될 수 있습니다. 그렇기 때문에 재귀함수를 설계할 때는 입력값이 종료 조건으로 수렴하는지 검증해야 합니다.

 

 

 

재귀 함수 예시

Java

// 최대 공약수 구하기
static int gcd(int a, int b) {
	if (a % b == 0) {
		return b;
	}
	return gcd(b, a % b);
}

// 피보나치 수열
static int fibo(int n){
	if(n == 0){
    	return 0;
    }

	if (n < 3) {
    	return 1;
    }
    
    return fibo(n - 2) + fibo(n - 1);

}