강의 보고 공부한 것을 정리하는 목적으로 작성된 글이므로 틀린 점이 있을 수 있음에 양해 부탁드립니다. (피드백 환영입니다)

우리가 최종적으로 A*알고리즘을 구현하기 위해서는
다익스트라를 알아야 하고 다익스트라를 알기위해서는
BFS를 알아야 하고 BFS를 알기위해서는
Graph를 알아야 하고 Graph를 알기위해서는
Tree를 알아야 하고 Tree를 알기위해서는
Vector/List를 알아야 한다.

음...
즉 Vector/List -> Tree -> Graph -> BFS -> Dijikstra -> A* (PQ(우선순위 큐))
이런식으로 알아야 한다.
우리는 Vector와 List에 대해서는 알아봤으므로 Tree에 대해서 알아봐야 하는데..
Tree에 대해 알기전에 재귀함수를 배우는 것이 좋기 때문에 재귀함수를 알아볼 것이다.

재귀함수란?

어떠한 함수가 있다.

void Func(int a)
{
	cout << a << endl;
    
    Func(a - 1);
}

이런식으로 함수 안에서 함수를 실행하는 함수이다.
이것이 재귀함수이다.
일단 우리는 생각할 수 있다.
이 함수를 실행하는 순간 크래시가 날 것이라는 것을

왜냐하면 스택에 함수를 호출하면 스택프레임이 만들어지는데 그 스택프레임이 해제되지 않고 계속 스택프레임이 만들어지기 때문에 결국 스택오버 플로우가 날 것이라는 것을 알 수 있다.

그래서 우리는 재귀함수를 사용할 때는 기재사항 즉 조건이 있어야 한다는 것을 알 수 있다.

위 코드에 조건을 넣어보자

void Func(int a)
{
	if(a <= 0)
    	return;
	cout << a << endl;
    
    Func(a - 1);
}

왜 쓸까?

코드의 가독성을 높이고 변수의 사용도 줄일 수 있다.
특히 Tree같은 경우 똑같은 함수를 재사용하면 상황을 묘사하기가 쉬워질 떄가 있다.

예제

팩토리얼 예제로 한 번 알아본다면
일단 팩토리얼의 규칙을 찾는다.
5! = 5 * 4!즉 n! = n * (n-1)!이라고 볼 수 있다.

그럼 만들어보자

int Factorial(int a)
{
	if(n <= 1)
    	return 1;
       
    return n * Factorial(n - 1);
}

정리

재귀함수는 솔직히 별거 없다.
만약 재귀함수가 이해가 되지 않는다면 러시아 인형(마트료시가?)그거를 생각하면 이해하기 편할 수도 있다.

일단 트리랑 그래프쪽에서 많이 사용된다라는 것을 알고 있으면 될 것 같다.