재귀 함수

C++ 재귀 함수 예제 분석

재귀 함수는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다. 이 기법은 복잡한 문제를 간결하고 이해하기 쉽게 해결할 수 있는 방법을 제공합니다. 이번 포스트에서는 다양한 재귀 함수 예제와 트리 순회 알고리즘을 살펴보겠습니다.

전체 코드

#include <iostream>

using namespace std;

void count(int n)
{
    // 재귀 함수는 탈출 조건을 만들어줘야 한다.
    if (n < 0)
        return;

    cout << "Count : " << n << endl;
    count(n - 1);
    cout << "Started : " << n << endl;
}

// 점화식은 재귀 함수로 표현 할 수 있다.
// fac(1) = 1
// fac(n) = n * fac(n - 1)
int fac(int n)
{
    if (n == 1)
        return 1;

    return n * fac(n - 1);
}

// fib(0) = fib(1) = 1
// fib(n) = fib(n - 1) + fib(n - 2)
int fib(int n)
{
    if (n <= 1)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

struct Node
{
    int value;
    Node* left;
    Node* right;
};

// tree preorder traverse
void visit(Node* root)
{
    if (root == nullptr)
        return;

    cout << root->value << endl;
    visit(root->left);
    visit(root->right);
}

int main()
{
    Node node0{ 0 };
    Node node1{ 1 };
    Node node2{ 2 };
    Node node3{ 3 };
    Node node4{ 4 };
    Node node5{ 5 };
    Node node6{ 6 };
    Node node7{ 7 };
    Node node8{ 8 };
    Node node9{ 9 };

    node0.left = &node1;
    node1.left = &node2;
    node1.right = &node3;
    node3.right = &node4;
    node0.right = &node5;
    node5.left = &node6;
    node6.right = &node7;
    node5.right = &node8;
    node8.left = &node9;

    visit(&node0);
}

//         n0
//   n1          n5
// n2   n3    n6     n8
//        n4    n7 n9

코드 분석

1. 헤더 파일 포함 및 네임스페이스 사용

   #include <iostream>
   using namespace std;

   • #include <iostream>: 표준 입력 출력 스트림을 포함합니다.
   • using namespace std;: std::를 생략하고 표준 라이브러리의 요소를 사용할 수 있게 합니다.

2. count 함수

   void count(int n)
   {
       // 재귀 함수는 탈출 조건을 만들어줘야 한다.
       if (n < 0)
           return;
   
       cout << "Count : " << n << endl;
       count(n - 1);
       cout << "Started : " << n << endl;
   }

   • 기능: 주어진 정수 n부터 0까지의 카운트를 출력하고, 재귀 호출이 끝난 후 다시 시작합니다.
   • 탈출 조건: n < 0일 때 함수가 종료됩니다.
   • 재귀 호출: count(n - 1)를 통해 자기 자신을 호출합니다.

3. 팩토리얼 함수

   int fac(int n)
   {
       if (n == 1)
           return 1;
   
       return n * fac(n - 1);
   }

   • 기능: 주어진 정수 n의 팩토리얼을 계산합니다.
   • 점화식: fac(n) = n * fac(n - 1)
   • 탈출 조건: n == 1일 때 함수가 종료되고 1을 반환합니다.

4. 피보나치 함수

   int fib(int n)
   {
       if (n <= 1)
           return 1;
       return fib(n - 1) + fib(n - 2);
   }

   • 기능: 주어진 정수 n의 피보나치 수를 계산합니다.
   • 점화식: fib(n) = fib(n - 1) + fib(n - 2)
   • 탈출 조건: n <= 1일 때 함수가 종료되고 1을 반환합니다.

5. 트리 노드 구조체 및 전위 순회 함수

   struct Node
   {
       int value;
       Node* left;
       Node* right;
   };
   
   void visit(Node* root)
   {
       if (root == nullptr)
           return;
   
       cout << root->value << endl;
       visit(root->left);
       visit(root->right);
   }

   • Node 구조체: 트리의 노드를 나타내며, 각 노드는 값과 좌우 자식 노드를 가집니다.
   • visit 함수: 트리를 전위 순회(preorder traverse)하며 각 노드의 값을 출력합니다.
   • 탈출 조건: root == nullptr일 때 함수가 종료됩니다.
   • 재귀 호출: visit(root->left)와 visit(root->right)를 통해 자식 노드를 방문합니다.

6. main 함수

   int main()
   {
       Node node0{ 0 };
       Node node1{ 1 };
       Node node2{ 2 };
       Node node3{ 3 };
       Node node4{ 4 };
       Node node5{ 5 };
       Node node6{ 6 };
       Node node7{ 7 };
       Node node8{ 8 };
       Node node9{ 9 };
   
       node0.left = &node1;
       node1.left = &node2;
       node1.right = &node3;
       node3.right = &node4;
       node0.right = &node5;
       node5.left = &node6;
       node6.right = &node7;
       node5.right = &node8;
       node8.left = &node9;
   
       visit(&node0);
   }

   • 기능: 트리 구조를 생성하고 visit 함수를 호출하여 트리를 전위 순회합니다.
   • 트리 구조:

             n0
       n1          n5
     n2   n3    n6     n8
            n4    n7 n9

   • 노드 연결: 각 노드를 적절히 연결하여 트리 구조를 형성합니다.