기록공간

재귀 또는 순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 재귀는 많은 문제들을 해결하는데 독특한 개념적인 해결책을 제공한다. 재귀를 이용하여 만든 재귀 함수는 어떻게 문제를 풀어가는지에 대해 직관적으로 알 수 있도록 해주어 가독성을 높인다는 장점이 있다. 하지만 단점도 존재한다. 함수를 호출하면 그 함수가 끝날때 어디로 복귀해야 한다는 복귀주소를 스택에 쌓게 되는데, 재귀함수는 재귀하는 횟수가 많아 질수록 이 쌓이는 복귀주소가 기하급수적으로 늘어나게 된다. 이로인해 스택 오버플로우가 발생하면 프로그램이 뻗는 현상이 나타난다. (이를 해결하기 위해 동적 계획법(Dynamic Programming)이라는 알고리즘을 사용한다) 재귀는 트리 구조에서 정말 많이 사용..