Java ch11-1 Recursion

Eden.Yang·2023년 6월 6일

Java

목록 보기

1/2

Recursion: a definition in terms of itself

-> 재귀(Recursion)를 스스로의 정의로 설명하는 것을 말합니다.

알고리즘에서 재귀는

반복되지만 실제로는 그렇지 않은 문제에 좋은 접근입니다.
문제를 해결하기 위한 규칙들을 차례 차례 거치는 알고리즘에 좋습니다.
하나 혹은 그 이상의 서브케이스를 풀기 위해 자기자신을 사용하는 알고리즘입니다.

특히나 자바에서 재귀는

재귀 알고리즘을 실행하기 위한 Recursive method입니다.
재귀 메소드는 자신을 향한 call을 포함한 정의입니다. 다시 말해, "메소드 정의 내에서 해당 메소드 자체를 호출하는 것"입니다.

재귀 메소드는 반드시 종료되어야 한다.

A recursive method must haveat least one base, or stopping, case
재귀 메소드는 적어도 하나 이상의 기본 또는 중단 조건을 가져야 합니다
A base case does not execute a recursive call; it stops the recursion.
기본 조건은 재귀 호출을 실행하지 않고 재귀를 중지시킵니다. 재귀 메소드는 자기 자신을 반복적으로 호출하는데, 각 호출은 이전 호출보다 작은 버전이어야 합니다. 이를 통해 언젠가는 기본 조건에 도달하게 됩니다. 기본 조건이 실행되면 재귀가 중지됩니다.
Each successive call to itself must be a 'smaller version of itself' so that a base case is eventually reached.
즉, 재귀 메소드는 주어진 문제를 더 작은 부분 문제로 분할하여 해결하기 위해 자기 자신을 호출합니다. 각 호출은 이전 호출보다 더 작은 입력 또는 인자를 전달하여 문제를 계속해서 작게 만들어 나갑니다. 이를 통해 재귀 호출이 반복되고, 기본 조건에 도달할 때까지 문제를 해결합니다.
An argument must be made smaller with each call so that eventually the base case executes and stops the recursion
재귀 메소드에서는 기본 조건이 반드시 실행되도록 해야합니다. 이를 위해 각 호출에서는 인자를 작게 만들어야 합니다. 작게 만들어진 인자들이 연속적으로 전달되면서 결국에는 기본 조건이 실행되어 재귀가 중지됩니다.

이러한 방식으로 재귀 메소드는 문제를 작게 분할하고 해결하는 동시에 재귀 호출을 제어하여 원하는 결과를 얻을 수 있습니다

한가지 sudo code를 통한 예시를 봅시다.

One way to search a phone book (which is an alphabeticallyordered list) for a name is with the following recursive algorithm: 전화번호부에서 이름을 검색하는 프로그램입니다.

Search:
middle page = (first page + last page)/2
Open the phone book to middle page;
If (name is on middle page)
then done;  //this is the base case
else if (name is alphabetically before middle page)
last page = middle page  //redefine search area to front half
Search//recursive call with reduced number of pages
else  //name must be after middle page
first page = middle page  //redefine search area to back half
Search//recursive call with reduced number of pages

위의 재귀 알고리즘은 알파벳순으로 정렬된 전화번호부에서 이름을 검색하는 방법 중 하나입니다.
Search 알고리즘은 다음과 같은 절차를 따릅니다:

중간 페이지를 계산합니다. (첫 번째 페이지 + 마지막 페이지) / 2
전화번호부를 중간 페이지로 엽니다.
만약 (이름이 중간 페이지에 있다면)
그것은 기저 사례(base case)이므로 검색을 종료합니다.
그렇지 않고, (이름이 중간 페이지 앞에 있다면)
마지막 페이지를 중간 페이지로 재정의합니다.
검색 영역을 앞쪽 절반으로 재정의합니다.
줄어든 페이지 수로 재귀 호출을 수행합니다. (Search 함수를 호출합니다.)
그렇지 않으면, (이름은 중간 페이지 뒤에 있다면)
첫 번째 페이지를 중간 페이지로 재정의합니다.
검색 영역을 뒤쪽 절반으로 재정의합니다.
줄어든 페이지 수로 재귀 호출을 수행합니다. (Search 함수를 호출합니다.)
이러한 방식으로 재귀 호출을 반복하면서 검색 영역을 점차적으로 줄여가고, 이름을 찾을 때까지 계속해서 검색을 진행합니다. 검색 알고리즘의 기저 사례는 이름을 찾은 경우로, 해당 경우에는 검색을 종료하고 결과를 반환합니다.

이 알고리즘은 이진 검색(Binary Search)의 재귀적인 형태로 구현되었으며, 알파벳순으로 정렬된 리스트에서 효과적인 검색을 수행할 수 있습니다.

또다른 예시, 이번에는 java코드를 통해 볼까요. Countdown 하는 간단한 프로그램입니다!

public class RecursiveCountdown
{
    public static void main(String[] args)
    {
        countDown(3);
    }
    public static void countDown(int num)
    {
        if (num <= 0)
        { 
            System.out.println();
        }
        else
        {
            System.out.print(num);
            countDown(num-1);
        }
    }
}

위의 코드는 재귀적인 방법을 사용하여 숫자를 역순으로 출력하는 예제입니다.

countDown 메소드는 정수 num을 매개변수로 받습니다. 메소드는 num이 0보다 작거나 같을 때까지 재귀적으로 호출됩니다.
이 코드에선 처음에 num의 값이 3으로 주어집니다. num이 0보다 작거나 같지 않으므로 else 블록이 실행됩니다.
먼저, System.out.print(num) 문장이 실행되어 현재 num의 값을 출력합니다. 그리고 countDown(num-1)을 호출하여 num의 값을 1만큼 감소시킨 후 다시 countDown 메소드를 재귀적으로 호출합니다.
이렇게 재귀 호출이 반복되면서 num의 값은 1씩 감소하고 출력되는 숫자는 역순으로 출력됩니다.
base case기저 사례는 num이 0보다 작거나 같을 때입니다. 이때는 아무 작업도 수행되지 않고, 빈 줄이 출력됩니다. 이를 통해 재귀 호출이 종료되고 메소드가 끝납니다.

따라서 위의 코드는 3부터 시작하여 3, 2, 1 순서로 출력하는 재귀적인 카운트다운을 수행합니다.
이를 도식화하면 아래와 같습니다.

자, 이번엔 여기에 Digit to Words 프로그램을 합쳐봅시다.

import java.util.Scanner;

    public class recursion
    {
        public static void main(String[] args)
        {
            System.out.println("Enter an integer:");
            Scanner keyboard = new Scanner(System.in);
            int number = keyboard.nextInt( );
            System.out.println("The digits in that number are:");
            displayAsWords(number);

            System.out.println( );
            System.out.println("If you add ten to that number, ");
            System.out.println("the digits in the new number are:");
            number = number + 10;
            displayAsWords(number);
            System.out.println( );
        }

        /**
        Precondition: number >= 0
        Displays the digits in number as words.
        */
        public static void displayAsWords(int number)
        {
            if (number < 10)
                System.out.print(getWordFromDigit(number) + " ");
            else //number has two or more digits
            {
                displayAsWords(number / 10);
                System.out.print(getWordFromDigit(number % 10) + " ");
            }
        }

        /**
        Precondition: 0 <= digit <= 9
        Returns the word for the argument digit.
        */
        private static String getWordFromDigit(int digit)
        {
            String result = null;
            switch (digit)
            {
                case 0: result = "zero";  break;
                case 1: result = "one";   break;
                case 2: result = "two";   break;
                case 3: result = "three"; break;
                case 4: result = "four";  break;
                case 5: result = "five";  break;
                case 6: result = "six";   break;
                case 7: result = "seven"; break;
                case 8: result = "eight"; break;
                case 9: result = "nine";  break;
                default:
                System.out.println("Fatal Error.");
                System.exit(0);
                break;
            }
    return result;
    }
}

이 코드는 사용자로부터 정수를 입력받고, 해당 정수의 각 자리 숫자를 영어 단어로 출력하는 프로그램입니다. 코드의 구조는 다음과 같습니다:
main 메소드:

사용자로부터 정수를 입력받습니다.
displayAsWords 메소드를 호출하여 입력받은 정수의 각 자리 숫자를 출력합니다.
입력받은 정수에 10을 더한 후 다시 displayAsWords 메소드를 호출하여 새로운 정수의 각 자리 숫자를 출력합니다.

displayAsWords 메소드:

주어진 숫자를 처리하여 각 자리 숫자를 출력합니다.
만약 숫자가 10보다 작으면, getWordFromDigit 메소드를 호출하여 해당 숫자의 영어 단어를 출력합니다.
숫자가 10 이상인 경우, 재귀적으로 displayAsWords 메소드를 호출하여 숫자를 자릿수 별로 분리하고 각 자릿수의 영어 단어를 출력합니다.

getWordFromDigit 메소드:

주어진 숫자에 해당하는 영어 단어를 반환합니다.
switch 문을 사용하여 숫자에 따라 영어 단어를 결정합니다.
주어진 숫자가 0부터 9까지의 범위를 벗어나는 경우, "Fatal Error."를 출력하고 프로그램을 종료합니다.

이 코드는 재귀(Recursion)를 활용하여 입력받은 정수의 각 자리 숫자를 처리하고 출력하는 예제입니다. 재귀적인 접근을 통해 숫자를 작은 단위로 분해하고 처리하기 때문에 코드가 간결하고 이해하기 쉽습니다.

좋은 Recursion(재귀)의 핵심

메소드 정의의 핵심은 if-else 문이나 다른 분기문이어야 합니다.
재귀 메소드는 분기문을 통해 여러 가지 경우를 처리할 수 있어야 합니다.
하나 이상의 분기에는 메소드의 재귀 호출이 포함되어야 합니다.
재귀 호출은 "더 작은" 인수를 사용하거나 "더 작은" 버전의 작업을 해결해야 합니다.
재귀적인 호출을 통해 작업을 작은 조각으로 나누고 해결하는 것이 핵심입니다.
하나 이상의 분기에는 재귀 호출이 포함되지 않아야 합니다. 이 부분은 중단 조건 또는 기저 사례(base case)입니다.

중단 조건은 재귀 호출을 멈추고 재귀 메소드의 실행을 종료하는 역할을 합니다.
재귀 호출이 없는 분기에서는 일반적으로 최종 결과를 반환하거나 다른 작업을 수행합니다.

무한 재귀 infinite recursion

만약 종료 조건이 없는 코드라면 어떨까요?
-> 프로그램은 컴퓨터가 resource를 다 소진할 때까지 지속될 겁니다(stack overflow).

Recursive vs Iterative Methods

All recursive algorithms/methodscan be rewritten without recursion
->모든 재귀 알고리즘과 메소드는 재귀 없이 작성할 수 있다.

재귀 대신 반복을 사용하여 메소드를 다시 작성하는 것을 "반복 메소드(iterative methods)"라고 합니다. 반복 메소드는 일반적으로 반복문을 사용하여 작성되며, 재귀 호출을 사용하는 것보다 실행 시간이 짧고 메모리 공간을 적게 사용합니다.

그렇다면 언제 재귀를 사용해야 할까요? 일반적으로 다음과 같은 경우에 재귀를 사용합니다:

효율성이 중요하지 않은 경우

재귀 호출은 반복보다 실행 시간과 메모리 사용량이 더 많을 수 있습니다. 따라서 재귀를 사용하는 것은 효율성이 중요하지 않은 경우입니다. 작은 규모의 문제나 알고리즘이나 재귀가 자연스럽게 적용되는 경우에 주로 사용됩니다.

코드를 이해하기 쉽게 만드는 경우

재귀는 문제를 작은 부분으로 분할하여 해결하기 때문에 문제의 구조나 동작을 더 직관적으로 표현할 수 있습니다. 특히 수학적이거나 재귀적인 구조를 가진 문제의 해결에 재귀가 적합합니다. 재귀를 사용하면 코드의 가독성과 이해도를 높일 수 있습니다.

따라서 재귀는 효율성이 크게 중요하지 않고 코드의 가독성과 이해도를 높이는데 중점을 둘 때 유용합니다. 재귀는 문제를 분할하여 해결하고, 재귀적인 구조를 갖는 문제에 적합한 프로그래밍 기법입니다. 그러나 큰 규모의 문제나 반복문으로 더 효율적으로 해결할 수 있는 경우에는 반복 메소드를 사용하는 것이 좋습니다.
위의 코드도 재귀없이 다시 작성할 수 있습니다.

import java.util.Scanner;
public class IterativeDemo
{
    public static void main(String[] args)
    {
        System.out.println("Enter an integer:");
        Scanner keyboard = new Scanner(System.in);
        int number = keyboard.nextInt( );
        System.out.println("The digits in that number are:");
        displayAsWords(number);
        System.out.println( );
        System.out.println("If you add ten to that number, ");
        System.out.println("the digits in the new number are:");
        number = number + 10;displayAsWords(number);
        System.out.println();
    }

/**Precondition: number >= 0
Displays the digits in number as words.
*/
public static void displayAsWords(int number)
{
    int divisor = getPowerOfTen(number);
    int next = number;
    while (divisor >= 10)
    {
        System.out.print(getWordFromDigit(next / divisor) + " ");
        next = next % divisor;
        divisor = divisor / 10;
    }
    System.out.print(getWordFromDigit(next / divisor) + " ");
}

 

// Precondition: n >= 0. 
// Returns 10 raised to the power n.

private static int getPowerOfTen(int n)  //987 -> 100
{
    int result = 1;
    while (n >= 10)
    {
        result = result * 10;
        n = n / 10;
    }
    return result;
}
// Precondition: 0 <= digit <= 9
// Returns the word for the argument digit.
    private static String getWordFromDigit(int digit)
    {
        String result = null;
        switch (digit)
        {
            case 0: result = "zero";  break;
            case 1: result = "one";   break;
            case 2: result = "two";   break;
            case 3: result = "three"; break;
            case 4: result = "four";  break;
            case 5: result = "five";  break;
            case 6: result = "six";   break;
            case 7: result = "seven"; break;
            case 8: result = "eight"; break;
            case 9: result = "nine";  break;
            default:
            System.out.println("Fatal Error.");
            System.exit(0);
            break;
        }
        return result;
    }
}

재귀 메서드는 반복적인 방법과 비교해 몇 가지 단점을 가지고 있습니다. 이는 실행 중에 재귀 호출과 함수 호출 스택 관리로 인한 오버헤드 때문입니다.
재귀 메서드가 호출될 때마다 호출 스택에 현재 메서드 호출에 대한 정보가 저장되는데, 이는 지역 변수, 매개변수, 반환 주소 등을 포함합니다. 재귀 호출마다 이러한 할당이 발생하며, 동일한 작업을 하는 반복적인 솔루션과 비교했을 때 메모리 사용량이 더 크게 될 수 있습니다.
또한, 재귀 메서드는 반복 호출 오버헤드로 인해 반복적인 해결책에 비해 더 느릴 수 있습니다. 각 재귀 호출은 함수 프레임 설정, 인수 전달 및 호출 스택 관리를 위한 추가 시간이 필요합니다. 이러한 오버헤드는 누적될 수 있으며, 깊거나 복잡한 재귀에 대해 더욱 느려질 수 있습니다.
그러나 이러한 단점에도 불구하고 재귀는 특정 프로그래밍 작업에서 더 나은 선택이 되기도 하며, 더 우아한 해결책을 제공할 수 있습니다. 재귀 알고리즘은 종종 문제의 내재적인 재귀적 구조를 반영하여 코드를 직관적이고 이해하기 쉽게 만들어줍니다. 재귀적인 해결책은 간결하게 표현되고 문제의 논리를 직접적으로 나타내므로 코드가 더 읽기 쉽고 유지보수가 용이해집니다.
또한, 특정 경우에는 재귀와 반복적인 해결책 간의 성능 차이가 메모리 사용량과 실행 시간 성능을 상쇄할만큼 크지 않을 수 있습니다. 문제의 특성, 제약 사항, 코드의 가독성과 유지보수성을 고려할 때, 재귀의 오버헤드가 무시할 정도로 작고, 더 우아한 해결책을 선택하는 것이 정당화될 수 있습니다.

효과적인 메모리 관리와 빠른 실행 속도가 중요한 경우에는 반복적인 해결책을 선택하는 것이 일반적입니다. 이는 특히 대규모 데이터 처리, 반복적인 계산 작업 또는 성능에 민감한 애플리케이션에서 유용합니다. 반복적인 알고리즘은 반복문을 사용하여 특정 작업을 반복하므로, 반복 호출 오버헤드가 없고 메모리 사용량이 작아집니다. 이로 인해 실행 속도가 더 빠르고 효율적인 알고리즘을 구현할 수 있습니다.
반면에 재귀는 주어진 문제가 재귀적인 구조를 가지고 있을 때, 코드의 가독성과 이해도를 높이는 데 도움이 됩니다. 재귀 알고리즘은 문제를 작은 하위 문제로 분할하고 각 하위 문제에 대해 재귀 호출을 수행하여 해결합니다. 이로 인해 코드가 더 간결하고 직관적이며, 문제의 본질에 집중할 수 있습니다. 특히 재귀적인 구조가 자연스럽게 문제를 해결하는 데 적합한 경우에는 재귀를 사용하는 것이 더 좋은 선택일 수 있습니다.
따라서 재귀를 선택하는 기준은 문제의 특성과 요구사항, 코드의 가독성과 유지보수성에 따라 다를 수 있습니다. 성능과 효율성이 우선이라면 반복적인 해결책을 고려해야 하지만, 코드의 가독성과 이해도가 더 중요하다면 재귀를 사용할 수 있습니다. 또한, 재귀와 반복 사이에서 최적의 해결책을 찾기 위해서는 문제의 크기와 입력에 따른 성능 테스트를 수행하고 비교해보는 것이 좋습니다.

마지막으로 return value가 있는 재귀함수 예시를 보겠습니다.

import java.util.Scanner;

public class recursion
{
    public static void main(String[] args)
    {
        System.out.println("Enter a nonnegative number:");
        Scanner keyboard = new Scanner(System.in);
        int number = keyboard.nextInt( );
        System.out.println(number + " contains " +getNumberOfZeros(number)+ " zeros.");
    }
    
/**
   Precondition: n >= 0
   Returns the number of zero digits in n.
*/
    public static int getNumberOfZeros(int n)
    {
        int result;
        if (n == 0)result = 1;
        else if (n < 10) result = 0;  
        //n has one digit that is not 0
        else if (n % 10 == 0)
        result = getNumberOfZeros(n / 10) + 1;
        else 
        //n % 10 != 0
        result = getNumberOfZeros(n / 10);
        return result;

    }
}