[JAVA] Recursion의 개념과 기본 예제

저는 아직 실력과 아는 게 너무 부족해서 프로그래밍 언어의 틀을 저의 기준에 개괄적으로 논할 자격이 없지만, 다른 실력자분들의 이야기를 들어보면 프로그래밍 언어를 구분하는 큰 틀 중에서

1. 절차 지향형 언어와

2. 객체 지향형 언어라는 구분이 있는 것 같습니다. 이 두 가지 개념 역시 칼로 무 베듯이 딱 떨어지는 개념은 아니겠지만, 최대한 단순하게 큰 특징만 뽑아서 나름의 비교를 해보자면 절차 지향형 언어란 C언어와 같이 프로그램이 어떤 순서와 절차에 의존하여 작동하고, 객체 지향형 언어란 C++, JAVA와 같이 클래스로 대표되는 객체들 사이의 상호작용에 의존하여 작동하는 프로그램을 대략적으로 의미합니다.

---

순환 함수는 자기 자신을 다시 호출하면서 반복 작업을 가능하게 하지만,

무한루프에 빠지는 걸 막아주는 Bsae Case를 반드시 가지고 있어야 합니다.

---

public class Recursrion1 {
    public static void main(String[] args){
        int n=4;
        System.out.println(func2(n));
    }

    public static void func(int k) {
        if (k <= 0)
            return;
        else {
            System.out.println("Hello...");
            func(k-1);
        }
    }

    public static int func2(int k){
        if(k<=0)
            return 0;
        else {
            return k+func2(k-1);
        }
    }
}

    public static int factorial(int n)
    {
        if(n==0)
            return 1;
        else
            return n*factorial(n-1);
    }

    public static int gcd(int p, int q){
        if(q==0)
            return p;
        else
            return gcd(q, p%q);
    }

---

Recursion은 위와 같은 수학 함수를 사용할 때뿐만 아니라, for문 등의 반복문을 대체하는 데에도 유용합니다.

    public static int length(String str){
        if(str.equals(""))  // 문자열 길이가 0
            return 0;
        else
            return 1+length(str.substring(1));  // 원래 문자열에서 앞의 문자열 하나를 제거
    }

    public static void printChars(String str){
        if(str.length()==0)
            return;
        else{
            System.out.println(str.charAt(0)); // 문자열의 인덱스 0의 문자 출력
            printChars(str.substring(1));
        }
    }

Recursion으로 문자열을 다룰 때에는, 주로 한 글자씩 원래의 문자열과 분리하고 다시 함수를 재귀 호출하는 방법을 사용합니다.

    public static void printCharsReverse(String str){
        if(str.length()==0)
            return;
        else{
            printCharsReverse(str.substring(1));
            System.out.println(str.charAt(0));
        }   // 가장 첫 글자가 마지막으로 호출
    }

바로 위에서 다룬 printChars와 비교해보면 매개변수를 포함하여 if문까지 동일하지만, else문에서 재귀 함수를 호출하는 코드와 첫 번째 문자열을 출력하는 순서만 바뀌어 있음을 알 수 있습니다.

---

    public static void printInBinary(int n){
        if(n<2)
            System.out.println(n);
        else{
            printInBinary(n/2);
            System.out.println(n%2);
        }
    }

10진수의 2진수 출력은 바로 위에서 다룬 문자열을 역순으로 출력하기와 비슷한 메커니즘을 가지고 있습니다. 10진수를 2진수로 표현하려면 2로 나눈 나머지를 역순으로 써야 하기 때문입니다.

---

    public static int sum(int n, int[] data){
        if(n<=0)
            return 0;
        else{
            return sum(n-1, data) + data[n-1];
        }
    }

---

    public static void readFrom(int n, int[] data, Scanner in){
        if(n==0)
            return;
        else{
            readFrom(n-1, data, in);
            data[n-1] = in.nextInt();
        }
    }

파일로부터 정수를 main영역의 배열에 저장하는 함수 역시, 재귀 호출을 통해 n-1에서 n-2, n-3,..1,0 순으로 접근한 뒤 다시 역순으로 돌아오며 배열에 값을 저장하는 구조입니다.

---

모든 순환함수는 결국 반복문(iteration)으로 변경이 가능합니다.

역시 모든 반복문도 recursion으로 표현이 가능합니다.

Recursion은 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 걸 가능하게 합니다.

하지만 함수 호출에 따른 오버헤드를 유발하는 문제점을 가지고 있습니다. 이는 프로그램 실행 속도에서의 손해로 이어집니다.