재귀함수

 

 

 

재귀함수

---

어떤 함수가 자신을 다시 호출하여 작업을 수행한다 (반복문)

 

 

 

재귀함수 예제

---

1 3 9 27 .. 의 n번째 수는 무슨 정수인가?

1 (1*3) (3*3) (3*3*3) .... 

n이 첫번째이면 결과값은 1 

recursion 함수를 실행하면 

함수에 n-1번째 값에 3을 곱한 값이다 

 

n이 4라면 

recursion(4-1) 3번째 수 (3*3) 에 3* 한 값  

static int recursion (int n) {
	if( n ==1) {
    	return 1;
    }
    return 3 * recursion(n-1);}

 

1 2 3 4 5 6 ... n번째 까지의 합 

 

static int recursion (int n) {
	if( n ==1) {
    	return 1;
    }
    return n + recursion(n-1);}

 

 

1 1 2 3 5 8 13 ...의 n번째 수  (피보나치 수열)

	// for문으로 찾기
    n = 6;
    result = 0; 
    int a =1;
    int b =1;
    
	if( n  < 3) {
    	result =1;
    }else {
    	for (int i =2; i < n; i++) {
        	result =a+b;
        	a =b;
        	b=result;
		}
    }
    return result;

재귀함수로 찾기

static int recursion (int n) {
	if( n  < 3) {
    	return 1;
    }
    return recursion(n-2) + recursion(n-1);}

 

 

 

팩토리얼을 재귀함수로 구현

static int recursion (int n) {
	if( n == 1) {
    	return 1;
    }
    return n * recursion(n-1);}

 

 

최대공약수를 재귀함수로 구현

static int recursion (int , int b) {
	if( a % b == 0) {
    	return b;
    }
    return recursion(b, a % b);