재귀 Recursive
어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다.
프로그래밍에서는 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법을 뜻한다. 재귀 호출이나 되부름이라고 불리기도 한다.
팩토리얼 factorial
팩토리얼을 구하는 문제를 풀어보기 전에 팩토리얼의 개념이 가물가물한 문돌이, 문순이들은 이 단락을 읽어보도록 하자.
- 팩토리얼의 정의
간단하게 말해 수를 단계적으로 곱한다는 것이다. 계승이라고도 한다. - 사용
n! = 1 x (···) x n
- 예시
3! = 1 x 2 x 3 = 6
5! = 1 x 2 x 3 x 4 x 5 = 120
- 단, 0! 은 1로 약속한다.
팩토리얼을 이해하기 쉬운 링크 첨부
https://terms.naver.com/entry.nhn?cid=58600&docId=3547109&categoryId=59193
느낌표가 수학 기호로도 쓰일까?
[ 1. 느낌표 모양의 수학 기호] 컴퓨터 키보드에서는 글자와 숫자 말고도 신기한 모양의 문자들을 볼 수 있어. 혹시 그중에서 수학 기호가 아닐까 하고 의심해 본 모양은 없니? 찌롱이가 수학 기호로 편지를 쓴 것처럼 세상에는 다양한 수학 기호들이 있단다. 그중에서 우리가 문장을 쓸 때 자주 사용하는 느낌표도 수학 기호라는 것 혹시 알고 있었니? 물론 수학에서 쓰는 느낌표는 그 이름도, 쓰임새도 완전히 달라. 수학에서 쓰는 ‘!’ 기호의 이름은 ‘팩토리얼’
terms.naver.com
팩토리얼 이해하기
a, b, c 세 개의 문자를 한 줄로 세우는 데 몇 가지 방법이 있을까? 경우의 수를 생각해보자.
- a가 맨 앞에 오는 경우 : abc, acb
- b가 맨 앞에 오는 경우 : bac, bca
- c가 맨 앞에 오는 경우 : cab, cba
a, b, c 세 개의 문자를 한 줄로 세우는 방법은 총 6가지이다. 하지만 굳이 이렇게 하나하나 일렬로 늘어놓지 않고도 답을 구할 수 있다. 바로 팩토리얼이다.
- 맨 앞에 올 문자 3가지 (a, b, c) ••• 3
- 두번째 올 문자 2가지 (맨 앞 제외 두 가지 문자) ••• 2
- 세번째 올 문자 1가지 (맨 앞, 두 번째 제외 나머지 문자) ••• 1
3 * 2 * 1 = 6
⇒ 3!
팩토리얼 구하는 메서드 구현
팩토리얼을 구하는 메서드를 만드려면 두 가지 규칙만 잘 기억하면 된다. 그리고 이를 메서드로 구현하면 된다.
- 0! = 1
- n > 0 이면 n! = n * (n-1)!
static int factorial(int n) {
if (n > 0){
return n * factorial(n - 1);
} else {
return 1;
}
}
class Factorial {
static int factorial(int n) {
if (n > 0)
return n * factorial(n - 1);
else
return 1;
}
public static void main(String[] args) {
int x = 5; // 5! 구하기
System.out.println(x + "의 팩토리얼은 " + factorial(x) + "입니다.");
}
}factorial 메서드 안에서 factorial메서드가 계속 해서 호출되는 이러한 형태를 재귀 호출(recursive call)이라고 한다.
factorial 함수에 5를 대입했을 때, 내부적으로는 5 * (4 * (3 * (2 * 1)))와 같은 형태를 갖추고 있다. 따라서 5! 의 값은 120이라는 결과를 얻을 수 있다.
댓글