알고리즘 1 : recursion
아니, 추석인데 과제있는거 진짜냐고....
아오
-------------------------------------------------------
1. 재귀
recursion : 자기 자신을 재참조하는 것
2. 여러가지 예제들
: 항상 탈출 조건이 있어야하며, 그렇지 않으면 무한 루프를 돌게 된다.
동적계획법에도 사용할 수 있다. (동적계획법은 다음 포스팅)
-factorial
|
1
2
3
4
5
6
7
|
unsigned int factorial(unsigned int n)
{
if (n <= 1)
return 1;
else
return n * factorial(n-1);
}
|
탈출조건 : n이 1보다 작으면 1을 반환 (즉, 0또는 1이면)
그 외에는 계속해서 n*factorial(n-1)
-fibonacci
입력 : 순열에서 몇 번째 숫자를 보고싶은지 (ex. 순열에서 3번째 숫자를 보고싶다-->3을 입력), n
출력 : n번째 숫자
*재귀는 항상 너무 복잡하게 생각하지 말 것
*물론 복잡하게 생각해야 할 때도 있지만, 결국은 컴퓨터에서 알아서 계산을 해 줄 것이기에,
탈출조건과 식만 생각하자
탈출조건 : 입력이 0이면 0, 입력이 1이면 1
피보나치의 식은 '첫번째 숫자+두번째 숫자 = 세번째 숫자'이기 때문에
f(n)=f(n-1)+f(n-2)가 된다
여기서 재귀를 통해 f(n-1)과 f(n-2)가 다시 따로 계산 시작
|
1
2
3
4
5
6
|
public int fibonacci(int n) {
if (n <= 1)
return n;
else
return fibo(n-2) + fibo(n-1);
}
|
-Tower of Hanoi
(수업에서 배우진 않았지만, 기본적으로 유명한 문제라고 하여 배워두면 좋다고 생각했다)
기본적인 규칙 : 한 번에 하나의 원판만 옮길 수 있다
큰 원판이 작은 원판 위에 있어서는 안된다.
문제 해결 방법 : 총 n개의 원판이 기둥 1에 있을 때,
기둥 1에서 n-1개의 원판을 기둥 2로 옮긴다.
기둥 1에서 마지막 1개의 원판을 기둥 3으로
기둥 2에서 n-1개의 원판을 기둥 3으로 옮긴다. -->재귀부분
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void move(int from, int to)
{
printf("\nmove from %d to %d", from, to);
}
void hanoi(int n, int from, int by, int to) //몇개의 원판을, 어디서, 어디를 거쳐서, 어디까지
//시작은 기둥1에서, 기둥2를 거쳐, 기둥3까지라고 해보자
{
if (n == 1)
move(from, to);
else
{
hanoi(n - 1, from, to, by); //n-1개의 원판을 기둥1 -> 기둥3을 거쳐서 -> 기둥2로
move(from, to); //1개의 원판을 일단 기둥1 -> 기둥3
hanoi(n - 1, by, from, to); //기둥2에 있는 남은 n-1개의 원판을 1을 거쳐 3으로 가야함
}
}
|
(위는 c코드)
(어렵네....파라미터가 3개나 되니까 좀 많이 어지럽다.....출력까지 있으니까 더 헷갈린다)
- 1부터 n까지 합 구하기
입력 : n
출력 : 총 합 (sum)
탈출조건 : n이 0이면, return 0
|
1
2
3
4
5
6
7
|
int sum(int n)
{
if (n <= 0)
return 0;
else
return n + sum(n-1);
}
|
간단하다...
개인적인 생각일 수 있지만...
뭔가 recursion은 탈출 조건만 잘 생각 + 식 생각만 잘 하면
이해가 쉬울 것 같은데...
또 생각처럼 쉽지는 않네..
이번 포스팅 : recursion의 기본 예제들
다음 포스팅 : 백준 내의 recursion문제들 + 동적계획법
고생했다!