재귀호출

재귀의 사전적 의미는 "원래 자리로 되돌아 가거나 되돌아 옴" 이라고 하고 있다.
또한 영어에서 재귀 대명사라는 말로 자기자신을 가리키는 뜻으로 사용하기도 한다.

이를 통하여 재귀호출은 자기 자신에게 돌아오는 처리라고 유추해 볼 수 있다.

한 마디로 정리하자면 재귀호출은 메서드가 자기 자신을 호출하도록 구현하는 형태이다.

#01. 팩토리얼 구하기

5! = 5 * 4 * 3 * 2 * 1

1) 반목문을 통한 구현

public class Factorial1{
    public static void main(String[] args) {
            // 팩토리얼을 구하기 위한 메서드 호출
        long result = getFactorial(5);
        // 결과출력
        System.out.println(result);
        }
    public static long getFactorial(int max){
        long result = 1;
        for (int i=max; i > 0; i--) {
            result *= i;
        }

        return result;
    }
}

출력결과

2) 재귀호출을 통한 구현

위의 유머에서의 두 가지 포인트는

계속해서 반복되는 내용이 등장한다.
끝도 없이 계속된다.

재귀호출은 마지막에 종료 조건을 명시하지 않는다면 무한루프에 빠지게된다. 그러므로 재귀호출을 구현할 때 가장 먼저 처리해야 할 것은 종료조건을 명시하는 것이다.

팩토리얼의 경우 주어진 값 부터 1까지만 1씩 감소하면서 곱하는 것이므로 조건값이 1보다 작거나 같다면 1을 리턴해야 한다. (곱셈에서의 1은 무의미 하기 때문)

    if(max <= 1) {
        return 1;
    }

팩토리얼의 수식을 분석해 본다면 다음과 같이 정의할 수 있다.

f(x) = x * f(x-1)

단, x가 1이하인 경우 1

Factorial2

public class Factorial2{
    public static void main(String[] args) {
        // 팩토리얼을 구하기 위한 메서드 호출
        long result = getFactorial(5);
        // 결과 출력
        System.out.println(result);
    }

    public static long getFactorial(int max){
        if(max <= 1){
            return 1;
        }

        return max * getFactorial(max - 1);
    }
}

출력결과

알고리즘이란?

알고리즘(라틴어, 독일어: Algorithmus, 영어: algorithm)이란 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다.

유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있다.

수학과 컴퓨터 과학에서 알고리즘이란 작동이 일어나게 하는 내재하는 단계적 집합이다.

알고리즘은 연산, 데이터 진행 또는 자동화된 추론을 수행한다.

수학의 공식으로 이해하자.

알고리즘의 조건

입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안됨)
명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.
효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.