자바 자료구조 첫 시간입니다!
오늘은 재귀호출 알고리즘에 대하여 공부해보겠습니다 :)
1. 재귀호출이란?
재귀호출(Recursive call)이란 함수 내부에서 자신을 또 다시 호출하는 행위를 말합니다.
이러한 재귀호출은 별다른 종결조건이 없을 경우 끊임없이 반복하여 자신을 호출하게 됩니다.
따라서, 함수 내부에는 함수 조건을 변화할 수 있는 명령문이 반드시 삽입되어야 합니다.
간단한 예제로 펙토리얼 함수를 들 수 있습니다.
!) 잠깐, 펙토리얼이란?
|
계승(Factorial) 보통 대한민국에선 계승이란 표현보단 소리나는 대로의 발음인 '펙토리얼'이라 읽고 표기한다. 기호로 표기할 때는 ' ! ' 느낌표 기호를 사용한다. n!은 1부터 n까지의 모든 자연수의 곱을 말한다. (단, n은 양의 정수) ex) 1! = 1 2! = 1 × 2 3! = 1 × 2 × 3 |
$$f_{(n)} = \begin{cases}1 & n = 0\\n\times f_{(n-1)} & otherwise \end{cases}$$
펙토리얼 함수의 경우 본인($f_{(n)}$)이 계속 호출되며 n의 값이 0이 될 경우 1을 호출하면서 끝나게 됩니다.
따라서, 종결조건 'n = 0' 을 갖는 재귀함수라 말할 수 있습니다.
2. 재귀함수의 종류
재귀함수는 '알고리즘이 호출될 때, 몇 회의 재귀호출이 일어나는지'를 기준으로 종류를 구분할 수 있습니다.
|
㉠ Linear Recursions ㉡ Binary Recursion ㉢ Multiple reculsion |
알고리즘이 호출될 때 최대 1회의 재귀호출 발생 알고리즘이 호출될 때 알고리즘이 호출될 때 다수(대부분 2회 초과)의 재귀호출 발생 |
3. 실전 재귀함수
다음으로는 실제로 많이 쓰는 재귀함수에 대하여 알아보겠습니다.
3-1. BinarySum
(여기서의 binary-sum은 이진법 덧셈이 아닙니다.)
pseudo code
|
1
2
3
4
5
6
7
|
Algorithm BinarySun (A, i, n) :
InPut : array A and int i and n
OutPut : sum of n int in A starting at i
if n = 1 then
return A[i]
else
return BinarySun (A, i, [n/2]) + BinarySun (A, i + [n/2], n/2)
|
cs |
- BinarySum 예시
|
sum(1, 2, 3, 4, 5, 6, 7, 8) → sum(1, 2, 3, 4) + sum(5, 6, 7, 8) → {sum(1, 2) + sum(3, 4)} + {sum(5, 6) + sum(7, 8)} → …… |
예제. 1 ~ 50까지의 숫자를 합산하는 BinarySum을 Java로 작성하시오.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
piblic class binarySum {
public static void main(String[] args) {
int[] arr = new int[50];
for(int i = 0; i < 50; i++) {
arr[i] = i+1;
}
binarySum bs = new binarySum();
System.out.println(bs.binarySum(arr, 0, 50));
}
public long binarySum(int[] A, int i, int n) {
if ( n == 1 ) {
return A[i];
}
else {
/*정수반환을 위하여 Math함수를 사용하였습니다.*/
return binarySum(A, i, (int)Math.ceil((float)n/2)) +
binarySum(A, i+(int)Math.ceil((float)n/2), n/2);
}
}
}
|
cs |
3-2. Fibonacci
피보나치 함수는 재귀호출을 사용하는 방식과 사용하지 않는 방식 두 가지 방식으로 함수를 만들 수 있습니다.
!) 잠깐, 피보나치란?
|
"어떤 남자가 벽으로 둘러싸인 장소에 한 쌍의 토끼들을 둔다. 만약 각 쌍이 두 번째 달부터 매달 토끼를 한 쌍씩 낳는다고 가정한다면 그 해에 얼마나 많은 쌍의 토끼가 생산되겠는가?" |
| 피보나치 수열을 생성하는 기본 규칙은 처음 두 항은 1이고, 세 번째 항부터는 바로 앞의 두 항의 합이 된다는 것이다. |
pseudo code : using Linear recursion
|
1
2
3
4
5
6
7
8
|
Algorithm Fib(n) :
Input : nonnegative integer n
Output : a pair Fibonacci numbers ( F_n, F_n-1)
if n <= 1 then
return (n, 0)
else
(i, j) = LinearFib(n - 1)
return ( i + j, i)
|
cs |
|
1
2
3
4
5
6
7
8
|
/*C언어입니다.*/
int fibo (int n)
{
if (n = 1 || n == 2)
return 1;
else
return fibo(n-2) + fibo(n-1);
}
|
cs |
pseudo code : using non-recursion
|
1
2
3
4
5
6
7
8
9
|
Algorithm Fib2(n) :
InPut : nonnegative integer n
OutPut : n th Finbonacci number F_n
if n <= 1 the return (n)
prev = 0, curr = 1
for 2 <= u <= n
next = curr + prev
prev = curr, curr = next
return next
|
cs |
최근댓글