알고리즘: 재귀함수 (1) Recursion

Recursion : 순환 혹은 재귀함수라 칭함

 

특징

    private void func(int n){
        if(n <= 0) return;	// base case
        else {
        	// recursive case
            func(n-1);
            System.out.printf("hello number %d\n", n);
        }
    }

 

1. 자기 자신을 호출하는 함수(메서드)
2. 재귀함수는 호출된 순서대로 메모리에 할당됨
3. 대표 예제. factorial, euclid, fibonacci ...

무한루프

• Base case : recursion에서 다시 recursion으로 돌아가지 않는 조건 필요
• Recursive case : recursion이 반복하다보면 base case로 수렴함

논리 구조

• 수학적 귀납법과 동일함

Recursive Thinking

 

-- Recursion은 수학함수 계산에만 유용한가? 

- 아니다. 수학함수뿐만 아니라 다른 문제들도 해결 가능함. 반복문을 이용해 하는 모든 일들을 Recursion을 활용해 해결 가능함

 

- 예시1. 문자열 길이 계산

    private int length(String str){
        // 만약 자른 String이 "" (공백)을 마주할 경우 0을 return
        if (str.equals("")) return 0;
        else {
            // substring(1)로 String의 index번호 1번부터 자름
            return 1 + length(str.substring(1));
        }
    }

 

 

-- 예시2. 문자열 프린트

입력으로 들어온 하나의 문자열을 화면에 출력

    private void printStr(String str){
        // str의 길이가 0일 경우 출력할 값이 없기에 return
        if (str.length() == 0) return;
        else {
            // 첫 문자를 출력한 뒤
            System.out.println(str.charAt(0));
            // 다음 문자열부터 잘라 넘겨줄것
            printStr(str.substring(1));
        }
    }

 

-- 예시3. 문자열을 뒤집어 프린트

원래 문자열을 거꾸로 출력 [ ★ 재귀함수가 메모리에 할당되는 것을 활용 ]

    private void printReverseStr(String str){

        if (str.length() == 0) return;
        else {
            // 재귀는 호출하며 메모리에 할당되며 base case를 만나면 할당된 역순으로 실행됨
            printReverseStr(str.substring(1));
            System.out.println(str.charAt(0));
        }

    }

 

-- 예시4. 이진수로 변환해 출력

이진수는 계산된 역순으로 출력됨. 이를 활용해 결과 값 출력

    private void printBinary(int n){
        if (n < 2) System.out.print(n);
        else {
            // 이진법은 계산된 역순으로 출력되기에 먼저 재귀함수를 호출함
            // 이진수의 몫 계산
            printBinary(n/2);
            System.out.print(n%2);
        }
    }

 

-- 예시5. 배열의 합 구하기

    // n: list 총 갯수
    private int arraySum(int n, int[] list){
        // 모든 리스트를 순회한 경우 0을 리턴함
        if (n <= 0) return 0;
        else {
            return arraySum(n-1, list) + list[n-1];
        }
    }

 

-- 예시 6. 데이터 파일로 n개의 정수 읽어오기

    // scanner로 n개의 정수를 입력 받아 배열 data에 저장
    private void readFrom(int n, int[] data){
        if (n <= 0) return;
        else {
            readFrom(n-1, data);
            data[n-1] = sc.nextInt();
        }
    }

index의 최대값은 n이며, 최소값은 0이다. 고로 재귀로 거꾸로 접근해 메모리에 할당하며 차례로 실행하여 0번 index부터 올라오며 값을 할당함. [ 하지만 굳이 리스트 값 할당은 재귀를 사용하지 않음 ]

 

Recursion VS Iteration

• 모든 순환함수는 반복문(iteration)으로 변경 가능
• 그 역도 성립함. 즉, 반복문은 Recursion으로 표현이 가능함 [ 반복문과 Recursion은 동일한 표현력을 가짐 ]
• 하지만 이 둘을 같다고 볼 수 없음.
• 순환함수는 복잡한 알고리즘을 경우에 따라 단순하고 알기 쉽게 표현하는 것을 가능하게 함
• 하지만 계속해서 함수를 호출하며 따른 오버헤드가 발생함 ( 매개변수 전달, 액티베이션 프레임 생성 등 )

오버헤드: 처리를 위해 들어가는 직.간접적인 시간.메모리 등을 이야기 함