[ 코드트리 조별과제 ] 프로그래밍 연습 - Chapter2. 재귀함수

 

재귀함수란? 정의된 함수 f가 해당 함수를 구현하는 데 동일한 함수 f를 다시 이용하게 되는 것을 말한다.

 

재귀함수에서는 종료조건을 올바르게 설정할때 무한 반복호출없이 올바르게 동작할 수 있다.

public class Main {
    public static void printStar(int n) { 
        if(n == 0)                        // n이 0이라면 퇴각 = 종료조건
            return;                      
            
        printStar(n - 1);                 // 1부터 n - 1번째 줄까지 출력하는 함수
        System.out.println("*****");      // n번째 줄에 해당하는 별 출력
    }

    public static void main(String[] args) {
        System.out.println("start");
        printStar(3);
        System.out.println("end");
    }
}

 

 

 1. 값을 반환하지 않는 재귀함수 

 

함수는 종료되는 순간 자신을 호출한 곳으로 반환된다. 그 이후의 작업이 수행된다.

 

 

또한 재귀함수에서 print의 위치도 중요하다.

함수의 호출전의 작업인가, 호출이후의 작업인가에 따라서 n의 값이 달라진다.

 

/* 반환전후 출력작업을 이용한 코드
N에서 1까지 1씩 감소하며 하나씩 출력했다가, 다시 1부터 N까지 1씩 증가하며 출력합니다.
ex) N N - 1 N - 2 N - 3.... 2 1 1 2 .... N - 1 N
*/

public class Main {
    public static void func(int n){
        if(n==0) return;
        System.out.print(n+" ");
        func(n-1);
        System.out.print(n+" ");
    }
    public static void main(String[] args) {
        func(n);
    }
}

 

 

public static void printStar(int n) {
    if(n == 0)
        return;
    
    for(int i = 0; i < n; i++)
        System.out.print("*");
    System.out.println();
    printStar(n - 1);
    for(int i = 0; i < n; i++)
        System.out.print("*");
    System.out.println();
}

 

printStar(3);

>> ***	// printStar(3) 첫출력
   **	// printStar(2) 첫출력
   *	// printStar(1) 첫출력 이후 printStar(0)으로 종료조건 달성
   *	// printStar(1) 반환 -> 두번째 출력
   **	// printStar(2) 반환 -> 두번째 출력
   ***	// printStar(3) 반환 -> 두번째 출력

 

 2. 값을 반환하는 재귀함수 

종료조건은 지극히 자명한, 계산 없이도 바로 결과를 알 수 있는 경우 로 설정하고 이후의 숫자의 증감에 따른 반복계산작업을 수행할 수 있다.

/*재귀함수로 구현한 팩토리얼*/
public static int fact(int n) {
    if(n == 1) return 1;
    return fact(n - 1) * n;
}

/*재귀함수로 구현한 각자리 숫자의 합*/
public static int F(int n) {
	if(n < 10) return n;
    return F(n / 10) + (n % 10);
}

 

점화식( 수열의 각 항을 그 이전의 항들과의 관계를 통해 정의하는 수학적 표현 )이 주어진 경우 n번째 수열의 값을 구하는 재귀함수 코드를 작성할 수 있다.

/*피보나치 수열값 구하기*/

public static int fibo(int n) { 
    // 첫 번째, 두 번째 원소는 1입니다.
    if(n <= 2) return 1;

    // 3번째 원소부터는 다음 점화식을 만족합니다.
    return fibo(n - 1) + fibo(n - 2);
}

 

 

재귀함수를 이용한 최소공배수