C_6. 재귀함수

6. 재귀함수

1. 재귀함수 (Recursiond function)

Bace Case - 기본 값, 무한루프에 빠지지 않게 한다. 

Recursive Case - 반복하다 base case로 빠진다. 

 

 

2. 재귀함수 활용

 

1) 팩토리얼 계산

int fn(n)
{
    if (n == 0)
	return 1;
    else
    	return n * fn(n-1);
}

2) 피보나치 계산

int fn(n)
{
    if (n == 0 || n == 1)
        return 1;
    else
        return (fn(n-1) + fn(n - 2));
}

3) 최대공약수 계산 간소화 (유클리드 메소드)

int fn(n, m)
{
    if (m < n)
    {
    	int temp = m;
    	n = m;
    	n = temp;
    }
    if (n == 0)
    	return m;
    else
    	return fn(n, m % n);
}

4) 거듭제곱 계산

int fn(int n, int x) // n: 거듭제곱할 수, x: 거듭제곱 횟수
{
    if (x == 0)
    	return 1;
    else
    	return (n * fn(n, x-1));
}

5) 제곱근 구하기

double fn(int n, int x) // n: 제곱근의 값을 구할 수, x: 재귀호출을 반복 수, x의 값이 클수록 정확도 높음. 
{
    if (n == 0)
        return 1;
    else
        return 2 + ((n - 1)/ (fn(n, x -1)));
}