자료구조 - 순환

[순환]

순환(재귀, Recursion)은 함수가 자기 자신을 호출하는 프로그래밍 기법입니다. 재귀는 문제를 작은 하위 문제로 나누어 해결하며, 각 하위 문제는 원래 문제와 유사한 구조를 가집니다. 재귀 함수는 보통 종료 조건(base case)을 가지고 있으며, 이 조건이 충족되면 재귀 호출을 멈춥니다.

 

코드 예시를 보겠습니다.

#include <iostream>

// 재귀적으로 팩토리얼을 계산하는 함수
int factorial(int n)
{
    if (n <= 1) 
    { // 종료 조건
        return 1;
    }
    else
    {
        return n * factorial(n - 1); // 재귀 호출
    }
}

int main()
{
    int number = 5;
    std::cout << "팩토리얼 " << number << " = " << factorial(number) << std::endl;
    return 0;
}

 

 

 

 

[반복 (Iteration)]

반복(Iteration)은 루프(반복문)를 사용하여 동일한 작업을 여러 번 수행하는 프로그래밍 기법입니다. 반복문은 일반적으로 for, while, do-while과 같은 구조를 사용하여 구현됩니다.

 

그리고 대부분의 경우 순환과 반복은 서로 변경이 가능합니다.

우의 순환 팩토리얼 코드를 반복으로 바꿔보겠습니다.

#include <iostream>

// 반복적으로 팩토리얼을 계산하는 함수
int factorial_iterative(int n) 
{
    int result = 1;
    for (int i = 1; i <= n; ++i) 
    {
        result *= i;
    }
    return result;
}

int main()
{
    int number = 5;
    std::cout << "팩토리얼 " << number << " = " << factorial_iterative(number) << std::endl;
    return 0;
}

 

 

 

 

[순환과 반복 차이점]

• 구현 방식: 재귀는 함수 호출을 통해 작업을 수행하며, 반복은 루프를 사용합니다.
• 성능: 재귀는 함수 호출 스택을 사용하기 때문에, 반복에 비해 메모리 사용량이 많고, 깊은 재귀 호출의 경우 스택 오버플로우가 발생할 수 있습니다. 반복은 비교적 메모리 효율적입니다.
• 가독성: 재귀는 문제를 분할하여 해결하는 자연스러운 방식을 제공하지만, 이해하기 어려울 수 있습니다. 반복은 직관적이며 이해하기 쉬운 경우가 많습니다.

 

 

추가적으로 피보나치 수열의 계산하는 프로그램을 순환과 반복으로 구현해보겠습니다.

 

<순환>

#include <iostream>

// 재귀적으로 피보나치 수를 계산하는 함수
int fibonacci_recursive(int n) 
{
    if (n <= 1) 
    { // 종료 조건
        return n;
    } 
    else 
    {
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2); // 재귀 호출
    }
}

int main()
{
    int number = 10;
    std::cout << "피보나치 " << number << " = " << fibonacci_recursive(number) << std::endl;
    return 0;
}

 

 

<반복>

#include <iostream>

// 반복적으로 피보나치 수를 계산하는 함수
int fibonacci_iterative(int n) 
{
    if (n <= 1)
    {
        return n;
    }
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; ++i) 
    {
        c = a + b;  
        a = b;
        b = c;
    }
    return b;
}

int main()
{
    int number = 10;
    std::cout << "피보나치 " << number << " = " << fibonacci_iterative(number) << std::endl;
    return 0;
}