[Algorithm] 재귀 (recursive)

재귀함수

재귀함수(再歸函數, recursion)

어떤 것을 정의할 대 자기 자신을 참조하는 것을 뜻한다.

즉 함수가 자기 자신을 계속 호출한다는 의미이다.

 

recursive라는 함수가 있다고 생각하자.

recursive는 자기 자신을 다시 호출한다.

함수 recursive(int x){
	recursive(int x + 1)
}

간단히 다음과 같은 방식을 따른다.

이를 그림으로 한번 보자.

재귀적 호출을 통해서 자신의 함수속에 또다른 함수를 실행하고 가장 늦게 실행된 함수부터 먼저 재귀 반환한다.

이번엔 예시코드로 동작 방식을 보자.

---

1. 재귀함수 동작 방식

재귀함수는 크게 4가지 방식을 따른다.

물론 이방법에서 순서는 코드에 따라서 변경될 수 있다.

1. 값을 받는다.
2. 종료 조건을 설정해서 종료될지 중지될지 정한다.
3. 받은 값으로 필요한 일을 한다.
4. 값을 넘겨준다. 넘겨준 값으로 1부터 다시 시작한다.

그럼 이 4 단계를 코드로 보자

1. 값을 받는다.

static void factorial(int x, int output)

x과 output이라는 값을 int형태로 받아온다.

2. 종료 조건을 설정해서 종료될지 중지될지 정한다.

if (x > 5){
    System.out.print(output);
    return;
}

출력할 값인 output에 x를 곱해주고

x의 숫자를 1 더해준다.

3. 받은 값으로 필요한 일을 한다.

int next_output = output * x;
int next_x = x + 1;

출력할 값인 output에 x를 곱해주고

x의 숫자를 1 더해준다.

4. 값을 넘겨준다.

factorial(next_x, next_output);

계산한 값은 x와 output을 넘겨준다.

전체적인 코드를 한번 보자

static void factorial(int x, int output){
    if (x > 5){
        System.out.print(output);
        return;
    }
    int next_output = output * x;
    int next_x = x + 1;
    factorial(next_x, next_output);
}

 

그럼 이번엔 값이 어떻게 이동하는지 보자

next값들이 재귀호출을 통해 다음 factorial에 들어가는 모습을 볼 수 있다.

factorial함수가 총 6번 실행된다.

그림으로도 한번 볼까?

빨간색 화살표가 각 함수가 다음 함수를 호출하는 방향이다.

next 즉 다음번 재귀함수에 들어갈 값들이 재귀적으로 호출한 함수로 들어간다.

마지막에 x가 5보다 크니 정지되고 120이 출력된다.

---

2. 재귀함수는 방식도 2개가 있다.

방금은 코드들이 아래쪽으로 내려가기만 했다 하지만 이번엔 return값을 이용해서 함수들을 다시 따라간다.

이걸 백트레킹이라고 부른다.

public static int factorial2(int x) {
    if (x == 1) {
        return 1;
    }
    int next_x = x - 1;
    return x * factorial2(next_x);
}

이번엔 return으로 돌아간다.

factorial(0)까지 함수가 안으로 들어가게 됐다가 return으로 나오게 된다.

빨간색은 재귀함수가 호출되며 값이 이동하는 방향

파란색은 값이 재귀 반환되며 값이 이동하는 방향이다.

---

3. 사실 재귀함수는 반복문과 비슷하다.

int factorial = 1;
for (int i = 1; i <= 5; i++) {
	factorial *= i;
}

위 for문을 보면 factorial에 계속 증가된 i값을 곱해준다. i가 5보다 커지면 종료된다.

반복해서 factorial를 호출하고 i값을 변경해 주는것이 비슷하지 않은가?

 

그런데 왜 재귀함수를 사용할까?

재귀호출을 통해서 코드를 간결하게 바꿀수 있고 가독성을 높일 수 있다.

특성	재귀 함수	반복문
목적	문제를 재귀적으로 해결	반복 작업을 제어
구현방식	함수 내에서 자기 자신을 호출	명시적인 반복 구조
코드의 간결성	종종 더 직관, 간결함	코드가 더 길어질 수 있음
기억 공간 사용	호출 스택을 사용해서 각 호출의 상태를 저장	반복문의 상태를 기록하기 위한 공간 추가 사용

(사실 그래서 시간, 공간 복잡도가 중요한 코딩 테스트에서는 재귀호출보다 반복문을 주로 사용하게 된다.)

 

---

4. 응용 해보자.

재귀함수가 뭔가요? 라는 문제를 풀어보자

17478번: 재귀함수가 뭔가요?

알려준 방식대로 설계를 한번 해볼까?

 

1. 값을 받는다.

static void recursive(int N, int count)

x과 output이라는 값을 int형태로 받아온다.

2. 종료 조건을 설정해서 종료될지 계속될지 정한다.

static void recursive(int N, int count){
    if (count == N){
		//N과 같을경우 종료
    }else{
    	//아니면 계속 진행
    }
}

count의 값이 N과 같아지면 종료된다.

3. 받은 값으로 필요한 일을 한다.

static void recursive(int N, int count){
    String line = "";  //N 값만큼 ____를 추가
    for (int i = 0; i < count; i++){
        line += "_____";
    }
    System.out.println(line+"재귀함수가 뭔가요?");
    
    if (count == N){ //count가 N일경우 함수 종료
		System.out.println(line+"재귀함수는 자기 자신을 호출하는 함수라네");
    }else{
    	System.out.println(line+"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
        System.out.println(line+"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
        System.out.println(line+"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
    }
    System.out.println(line+"라고 답변하였지.");
}

출력할 값들을 적어준다.

4. 값을 넘겨준다.

static void recursive(int N, int count){
    String line = "";
    for (int i = 0; i < count; i++){
        line += "_____";
    }
    System.out.println(line+"재귀함수가 뭔가요?");
    
    if (count == N){
		System.out.println(line+"재귀함수는 자기 자신을 호출하는 함수라네");
    }else{
    	System.out.println(line+"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
        System.out.println(line+"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
        System.out.println(line+"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
    
        recursive(N, count + 1); // 재귀함수 호출
    }
    System.out.println(line+"라고 답변하였지.");
}

재귀 함수를 호출해준다.

 

전체코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
        recursive(N,0);
    }
    static void recursive(int N, int count){
        String line = "";
        for (int i = 0; i < count; i++){
            line += "____";
        }
        System.out.println(line+"\"재귀함수가 뭔가요?\"");
        if (count == N){
            System.out.println(line+"\"재귀함수는 자기 자신을 호출하는 함수라네\"");
        }
        else{
            System.out.println(line+"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
            System.out.println(line+"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
            System.out.println(line+"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
            recursive(N, count + 1);
        }

        System.out.println(line+"라고 답변하였지.");
    }
}