쭈쌤
쭈쌤 Hello World

[Java] 재귀호출

크리에이티브 커먼즈 라이선스 ITPAPER(호쌤,쭈쌤)에 의해 작성된 ≪[Java] 재귀호출≫은(는) 크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제 라이선스에 따라 이용할 수 있습니다.
이 라이선스의 범위 이외의 이용허락을 얻기 위해서는 leekh4232@gmail.com으로 문의하십시오.

[Java] 재귀호출

재귀의 사전적 의미는 “원래 자리로 되돌아 가거나 되돌아 옴” 이라고 하고 있습니다. 이를 통하여 재귀호출는 자기 자신에게 돌아오는 처리라고 유추해 볼 수 있겠습니다. 한마디로 정리하자면 재귀호출은 메서드가 자기 자신을 호출하도록 구현하는 형태입니다.

인터넷에서의 프로그래머들을 위한 유머 중

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.

“재귀함수가 뭔가요?”

“잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네.
그런데 어느날, 그 선인에게 한 선비가 찾아와서 물었어.
“재귀함수가 뭔가요?”

“잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네.
그런데 어느날, 그 선인에게 한 선비가 찾아와서 물었어.
“재귀함수가 뭔가요?”

“잘 들어보게. …”

#01. 팩토리얼 구하기

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

1) 반복문을 통한 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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. 계속해서 반복되는 내용이 등장한다.
  2. 끝도 없이 계속된다.

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

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

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

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

f(x) = x * f(x-1)
단, x가 1 이하인 경우 1

Factorial2.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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);
    }
}

#02. 총 합 구하기

양의 정수 n을 입력 받아 1부터 n까지의 총 합을 구하는 기능을 재귀함수로 구현하시오.

n부터 1씩 감소하면서 합산을 하고 1이 되는 순간 더 이상 진행하지 않고 종료해야 한다.

예를 들어 n이 5일 때, 5 + 4 + 3 + 2 + 1이 되어야 한다.

이를 수식으로 표현하면 다음과 같다.

1
2
f(1) = 1
f(n) = n + f(n-1)

이 수식을 프로그램으로 구현한 결과는 아래와 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Scanner;

public class MySum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("양의 정수를 입력하세요: ");
        int n = sc.nextInt();

        int s = sum(n);
        System.out.println("결과값: " + s);
    }

    public static int sum(int n) {
        if (n == 1) {
            System.out.println(n);
            return 1;
        }

        System.out.print(n + " + ");
        return n + sum(n-1);
    }
}
출력결과
1
2
3
4
5
6
7
8
9
10
11
12
13
14
T:\>java MySum
양의 정수를 입력하세요: 5
5 + 4 + 3 + 2 + 1
결과값: 15

T:\>java MySum
양의 정수를 입력하세요: 7
7 + 6 + 5 + 4 + 3 + 2 + 1
결과값: 28

T:\>java MySum
양의 정수를 입력하세요: 10
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1
결과값: 55

#03. 구구단

파라미터로 전달된 값에 대한 구구단 수식을 1부터 9까지 출력하는 재귀함수.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Gugu {
    public static void main(String[] args) {
        printGugu(7, 1);
    }

    public static void printGugu(int level, int depth) {
        if (depth > 9) {
            return;
        }

        System.out.printf("%d x %d = %d\n", level, depth, level*depth);
        printGugu(level, depth+1);
    }
}
출력결과
1
2
3
4
5
6
7
8
9
7 x 1 = 7
7 x 2 = 14
7 x 3 = 21
7 x 4 = 28
7 x 5 = 35
7 x 6 = 42
7 x 7 = 49
7 x 8 = 56
7 x 9 = 63

#04. 피보나치 수열

피보나치 수는 다음과 같은 초기값 및 점화식으로 정의되는 수열이다.

1
2
3
F(0)=0
F(1)=1
F(n)=F(n-1)+F(n-2)

n값이 2부터 증가하는 동안 다음과 같이 표현된다.

1
2
3
4
5
F(2) = 0 + 1 = 1
F(3) = 1 + 1 = 2
F(4) = 1 + 2 = 3
F(5) = 2 + 3 = 5
F(6) = 3 + 5 = 8

f.png

Fibo.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Fibo {
    public static void main(String[] args) {
        // 0부터 8까지의 피보나치 수 모두 출력
        for (int i=0; i<9; i++) {
            System.out.printf("%d\t", fibo(i));
        }
    }

    public static int fibo(int n) {
        // 전달받은 값과 동일한 값을 리턴한다면 계산할 필요가 없으므로 중단
        if (n <= 1) {
            return n;
        } else {
            return fibo(n-2) + fibo(n-1);
        }
    }
}
출력결과
1
0   1   1   2   3   5   8   13  21

크리에이티브 커먼즈 라이선스 ITPAPER(호쌤,쭈쌤)에 의해 작성된 ≪[Java] 재귀호출≫은(는) 크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제 라이선스에 따라 이용할 수 있습니다.
이 라이선스의 범위 이외의 이용허락을 얻기 위해서는 leekh4232@gmail.com으로 문의하십시오.

comments powered by Disqus