[JAVA] 재귀 호출

재귀 호출이란?

   메소드 내에서 메소드 자기 자신을 호출하는 방식을 재귀 호출이라 하고, 이러한 특징을 재귀라 함

 

    [ 특징 ]

    1. 코드가 간결하며, 오류 수정이 용이

    2. 실행 시간 관점에서는 처리 속도가 느려 반복문보다 비효율적

    3. 하나 이상의 종료 조건을 사용하여 재귀 호출을 종료하도록 한다 ( 기저 조건 )

    4. 모든 재귀 호출은 원 문제를 부분 문제로 줄여가면서 종료 조건이 될 때까지 반복

 

 

 

 

# 무한 반복되는 재귀 호출

    함수 호출은 메모리의 Stack영역을 사용하므로 무한 반복되는 재귀 호출은 java.lang.StackOverflowError를 유발

 

 

 

 

# 재귀 호출을 이용한 프로그램 예)

    - 계승 구하기, 하노이 탑, Quick 정렬 및 병합 정렬 등의 알고리즘, 파일 찾기 프로그램 등

 

 

 

재귀 호출 예

 

 

위의 예제 그림 설명

 

 

 

 

# 여러가지 재귀 메소드

package ex0804;
 
public class Recursion_Ex3 {
    public static void main(String[] args) {
        
        User9 u = new User9();
        double a;
        
        a = u.pow(2,10); //1024
        System.out.println(a);
        
        
        a = u.pow(2,-2); //0.25
        System.out.println(a);
        
        
        System.out.println((u.gcd(12, 16))); //4
        
        
        for(int i = 1; i<10; i++) {
            System.out.printf("%3d",u.fibo(i));
        }
        System.out.println();
    }
}
 
 
 
class User9{
    
    
    //a의 b승 구하기    
    /*
    public double pow(int a, int b) {
        return b>1 ? a*pow(a,b-1) : a; //2의 -2승은 안됨 
    }*/
    
    public double pow(int a, int b) {
        if(b>=0) {
            return b>0 ? a*pow(a,b-1) : 1;
        }
        else {
            return (1.0/a)*pow(a,b+1); // 1/a를 몇번했는지
        }
    }
    
    
    
    //최대공약수 구하기
    public int gcd(int a, int b) {
        return b==0?a:gcd(b,a%b);
    }
    
    
    
    
    //피보나치수열구하기
    public int fibo(int n) {
        if(n<2) {
            return n;
        }
        return fibo(n-1)+fibo(n-2);
    }
    
    
}