[자료구조][재귀 Recursion] 팩토리얼 , 피보나치 , 하노이탑 :: seoftware

윤성우의 열혈 자료구조를 참고하여 쓰는 글입니다.

 

오늘부터 열심히 살려고 블로그 글 처음 쓰는데,, 실수로 뒤로가기 버튼 눌러버림,, 없어짐,, 눈물남,, 이제는 간단하게 쓸거야ㅜㅜ

---

 

정의 재귀함수란 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다.

void Recursive(void) {
    cout << "Recursive call!" << endl;
    Recursive() //이런 것이 재귀! 자기 재호출
}

Recursive 라는 함수 안에서 Recursive가 다시 불리는데, 이런 함수를 재귀함수라고 한다.

다만 여기서 문제는 종료조건이 없다는 것이다. 위의 함수를 call한다면 무한루프에 빠지게 될 것이다.

따라서 위 코드는 다음과 같이 수정되어야 한다.

#include <iostream>
using namespace std;

void Recursive(int num) {
    if(num <= 0) return;
    cout << "Recursive call - " << num << endl;
    Recursive(num-1);
}
int main(void) {
    Recursive(3);
    return 0;
}

Recursive 함수 안에 있는 if문이 종료 조건이 된다. 파라미터 num이 0이 되면 재귀함수 종료!

 

재귀함수의 예시로 팩토리얼, 피보나치수열, 하노이의 탑을 들 수 있다.

 

예시1 팩토리얼 Factorial

 

팩토리얼 수식  :  n! = n * (n-1) * (n-2) * ··· * 2 * 1

예시 : 5! = 5 * 4 * 3 * 2 * 1 = 120

 

이는 n! = n * (n-1)! 로 표현 할 수 있다. 

함수로 표현하면  f(n) = n * f(n-1) (n>=1, f(0) = 0) 이므로 재귀함수의 특성을 만족한다.

 

코드로 구현하면 다음과 같다.

/* Factorial */
#include <iostream>
using namespace std;

int Factorial(int n) {
    if(n==0) return 1;
    else return n*Factorial(n-1);
}
int main(void) {
    cout << "1! = " << Factorial(1) << endl;
    cout << "5! = " << Factorial(5) << endl;
    cout << "9! = " << Factorial(9) << endl;

    return 0;
}

 

예시2 피보나치 수열 Fibonacci Sequence

 

피보나치 수열 : 앞에 수 두 개를 더한 것이 현재의 수인 수열

수식 : n번째 값 = n-1 번째 값 + n-2 번째 값

예시 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 · · · 

 

함수로 표현하면  fib(n) = fib(n - 1) + f(n - 2) (n>2, fib(1) = 0, fib(2) = 1) 이므로 재귀함수의 특성을 만족한다.

 

이를 코드로 구현하면 다음과 같다.

/* Fibonacci Sequence */
#include <iostream>
using namespace std;

int fibo(int n) {
    if(n==1) return 0;
    else if(n==2) return 1;
    else return fibo(n-1) + fibo(n-2);
}
int main(void) {
    for(int i = 1; i<10; i++) {
        cout << fibo(i) << " ";
    }
    return 0;
}

 

예시3 하노이의 탑 The tower of Hanoi

하노이의 탑 설명 : 위의 그림과 같은 세 개의 막대에 크기가 모두 다른 원판이 꽂혀 있다. A에서 C까지 모든 원판을 옮기는 것이 목표이고, 옮기는 과정에서 큰 원반이 작은 원반 위에 올려져서는 안된다.

 

예시 : 원판 4개가 있다고 가정해보자.

        과정 1. 작은 원반 3개(맨 아래 것을 제외한 모두)를 A에서 B로 이동

        과정 2. 큰 원반(맨 아래 원판)을 A에서 C로 이동

        과정 3. 작은 원반 3개(과정1에서 B로 옮긴 원반들)를 B에서 C로 이동

이를 일반화하여 표현하면

        과정 1. 작은 원반 n-1개(맨 아래 것을 제외한 모두)를 A에서 B로 이동

        과정 2. 큰 원반 1개를 A에서 C로 이동

        과정 3. 작은 원반 n-1개를 B에서 C로 이동

 

n개의 원반을 옮기기 위해, n-1, n-2, · · · , 1 개의 원반을 옮겨야하는 과정이 필요하므로 재귀를 사용한다.

 

이를 구현한 코드는 다음과 같다.

/* The tower of Hanoi */
#include <iostream>
using namespace std;
void hanoi(int num, char from, char by, char to) {
    if(num == 1) cout << "원반1을 " << from << "에서 " << to << "로 이동" <<endl;
    else {
        hanoi(num-1, from, to, by);
        cout << "원반" << num << "을 " << from << "에서 " << to << "로 이동" <<endl;
        hanoi(num-1, by, from, to);
    }
}
int main(void) {
    //막대 A에 있는 3개의 원판을 C로 옮기기
    hanoi(3, 'A', 'B', 'C');
    return 0;
}