알고리즘 1 : recursion

아니, 추석인데 과제있는거 진짜냐고....
아오

-------------------------------------------------------


1. 재귀
recursion : 자기 자신을 재참조하는 것

너무 귀엽다 진짜

2. 여러가지 예제들
: 항상 탈출 조건이 있어야하며, 그렇지 않으면 무한 루프를 돌게 된다.
  동적계획법에도 사용할 수 있다. (동적계획법은 다음 포스팅)



-factorial

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)가 다시 따로 계산 시작

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으로 옮긴다. -->재귀부분

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

int sum(int n)
 {
     if (n <= 0)
         return 0;
     else
         return n + sum(n-1);
 }

간단하다...





개인적인 생각일 수 있지만...
뭔가 recursion은 탈출 조건만 잘 생각 + 식 생각만 잘 하면
이해가 쉬울 것 같은데...
또 생각처럼 쉽지는 않네..


이번 포스팅 : recursion의 기본 예제들
다음 포스팅 : 백준 내의 recursion문제들 + 동적계획법

고생했다!