C++ 함수 - 재귀함수

함수 내부에서 함수가 자기 자신을 또 다시 호출하는 것
재귀 호출을 중단할 조건문이 없다면 끝없이 반복되므로 조건이 변경될 명령문이 필요하다

#include <iostream>

using namespace std;

int cnt = 0;

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

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

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

void count(int n) {
	if (n < 0)
		return;
	cout << n << " " << cnt++ << endl;
	count(n - 1);
	// n >= 0 일때 위 구간이 반복 실행됨
	cout << n << " " << --cnt << endl;
	// n < 0 일때 실행됨
}

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

int main() {
	count(3);
	cout << endl;
	cout << "5! = " << fac(5) << endl;
	cout << "fibonacci 5 th = " << fib(5) << endl;
	cout << endl;

	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;
	node5.right = &node8;
	node8.left = &node9;

	visit(&node0);
    
    return 0;
}

• 코드 실행 결과

  3 0
  2 1
  1 2
  0 3
  0 3
  1 2
  2 1
  3 0
  
  5! = 120
  fibonacci 5 th = 8
  
  0
  1
  2
  3
  4
  5
  6
  8
  9

노드의 트리 구조를 시각화한것