[Java] 재귀 용법(recursive call)의 개념과 사용 방식 (예제 / 문제 풀이)

서론

---

이번 포스팅에선 재귀용법의 개념과 예제를 통해 사용 방식에 대해 학습해보려한다. 바로 알아보자

 

---

 

재귀 용법(recursive call)이란?

---

• 함수 안에서 동일한 함수를 호출하는 형태를 말한다.
• 여러 알고리즘 풀이 시 자주 사용되므로 꼭 알고 넘어가야하는 것 중 하나이다.
• 재귀 호출은 스택 형식을 갖는다.

위와 같이 재귀 함수는 내부적으로 스택 형식으로 관리된다.

 

---

 

재귀 호출의 일반적인 형태는?

---

예제를 들어가기 앞서 코드 레벨로 기본적인 재귀 형태에 대해서 알아보자

[형태1]

function(입력) {
    if (입력 > 일정값) {                       // 입력이 일정 값 이상이면
        return function(입력 - 1);           // 입력보다 작은 값
    } else {
        return 특정값; // 재귀 호출 종료
    }
}

[형태2]

function(입력) {
    if (입력 <= 일정값) {                       // 입력이 일정 값보다 작으면
        return 특정값              // 재귀 호출 종료
    } 
    return function(입력 - 1);
}

재귀형식은 위와 같은 형태를 기본적으로 갖고 간다 생각하면 된다. 두 형태의 차이는 입력값의 범위에서 차이가 있다고 보면 되고, 본인의 스타일과 형식에 맞는대로 틀을 가져가주면 될 것 같다.

 

---

 

예제

---

Q. 팩토리얼을 재귀함수를 통해 구해볼 것

 public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        System.out.println(factorialFunc(num));
 }

 public static int factorialFunc(int n) {
        if (n > 1) {
            return n * this.factorialFunc(n - 1);
        } else {
            return 1;
        }
 }

 

해당 코드의 시간 복잡도와 공간 복잡도는?

• f(n)은 fn-1번의 factorialFunc() 함수를 호출해서 곱셉을 한다.
  • 일종의 n-1번 반복문을 호출한 것과 동일하다.
  • factorialFunc() 함수를 호출할 때마다 지역변수 n이 생성된다.
• 시간/ 공간 복잡도는 O(n-1)이므로 결국 둘 다 O(n)이 된다.

 

추가 문제

해당 내용 확립을 위해 아래의 URL에 있는 문제를 재귀형식으로 풀어보기 권장한다.

https://www.acmicpc.net/problem/9095

 

 

마무리

---

이번 포스팅에선 간단히 재귀용법에 대해 알아보는 시간이였고, 이 재귀 용법은 추 후 고급 정렬 알고리즘에서도 많이 사용되기에 알고가는 것이 좋습니다. 

 

추가 문제는 백준에서 DP로 분류가 되어있지만 재귀 용법을 통해 구현해보시면 재귀에 대한 개념 이해에 크게 도움 될 것이라 생각합니다.

 

문제 풀이는 아래의 URL을 통해 확인할 수 있습니다. 

https://jeongkyun-it.tistory.com/190