Recursion - 순환함수(재귀함수) (2)

2021/03/01 - [개발/알고리즘 기초공부] - Recurtion - 순환함수(재귀함수) (1)

2021/03/02 - [개발/알고리즘 기초공부] - Recursion - 순환함수(재귀함수) (3)

2021/03/02 - [개발/알고리즘 기초공부] - Recursion - 미로찾기

2021/03/04 - [개발/알고리즘 기초공부] - Recursion - Blob 셀 카운트

 

    //문자열 길이 계산
    public static int length(String str){
        if (str.equals("")) return 0;
        else return 1+length(str.substring(1));
    }

    //문자열 프린트
    public static void printChars(String str){
        if (str.equals("")) {
            System.out.println("");
            return;
        }
        else {
            System.out.print(str.charAt(0));
            printChars(str.substring(1));
        }
    }

    //문자열을 뒤집어 프린트
    public static void printReversChars(String str){
        if (str.equals("")) return;
        else {
            printReversChars(str.substring(1));
            System.out.print(str.charAt(0));
        }
    }

    //2진수로 변환하여 출력
    public void printInbinary(int n){
        if (n<2) System.out.print(n);
        else {
            printInbinary(n/2);
            System.out.print(n%2);
        }
    }

    //배열의 합 구하기
    public static int sum (int n, int[] data){
        if(n<=0) return 0;
        else return sum(n-1, data) + data[n-1];
    }

    //데이터파일로부터 n개의 정수 읽어오기
    //Scanner in 이 참조하는 파일로부터 n개의 정수를 입력받아 배열 data의 
    //data[0], data[1],....,data[n-1]에 저장한다
    public void readFrom(int n, int[] data, Scanner in){
        if (n==0) return;
        else {
            readFrom(n-1, data, in);
            data[n-1] = in.nextInt();
        }
    }

 

Recursion vs Iteration

- 모든 순환함수는 반복문으로 변경 가능

- 그 역도 성립함. 즉 모든 반복문은 순환함수로 표현 가능

- 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 함

- But, 함수 호출에 따른 오버해드가 있음 (매개변수 전달, 액티베이션 프레임 생성 등)