[자료구조] 재귀(Recursion)

재귀(Recursion)

 

재귀(再歸, Recursion)는 수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 주로 이 방법은 함수에 적용한 재귀 함수(Recursion Function)의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다. 

 

즉, 자기 자신을 반복하여 호출한다고 보면 쉬울 것 같습니다.

#include <iostream>
 
using namespace std;
 
void RecursiveFunction(int num)
{
    if (num >= 10)
    {
        cout << "재귀 호출 끝" << endl;
        return;
    }
    else
    {
        cout << "Recursive = " << num << endl;
        RecursiveFunction(num + 1);
    }
}
 
void main()
{
    RecursiveFunction(0);
}

 

[실행 결과]

 

 

위에 코드만 봐도 쉽게 이해가 될 것 같습니다,

재귀 함수를 공부 할때 피보나치 수열을 많이 구현하는데 재귀의 흐름과 더불어 재귀의 표현을 익히기 좋기 때문인 것 같습니다.

 

피보나치 수열이란 간단하게 "앞에 2개의 수를 더한 수가 현재의 숫자"라는 간단한 규칙입니다.

그럼 수는 0과 1부터 시작하기 때문에 조건은 아래와 같습니다.

 

* 피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다. 

 

[구현]

#include <iostream>
 
using namespace std;
 
int Fibonacci(int num)
{
    if (num == 1)
    {
        return 0;
    }
    else if (num == 2)
    {
        return 1;
    }
    else
    {
        return Fibonacci(num - 1) + Fibonacci(num - 2);
    }
}
 
void Fibonacci_Sequence(int count)
{
    for (int i = 1; i < count; i++)
    {
        cout << Fibonacci(i) << " - ";
    }
 
    cout << "End" << endl;
}
 
void main()
{
    Fibonacci_Sequence(12);
}

 

[실행 결과]