저희 자료구조 / 알고리즘 스터디는 이번에 재귀 용법에 대해서 강의를 듣고 공부했습니다.
이 재귀 용법은 지난 주 정렬 알고리즘 스터디를 하면서 합병 정렬 알고리즘에 대한 문제를 풀 때, 이 재귀 용법을 사용했습니다.
다시 한 번 이 재귀 용법에 대해서 간단하게 설명하겠습니다.
재귀
재귀 함수는 Recursive Function이라고 해서, 함수 안에서 동일한 함수를 호촐하는 형태입니다.
재귀는 지난 주에 제가 합병 정렬을 구현할 때, 이 재귀를 통해 구현하였으며, 이 처럼 여러 알고리즘 구현 시 사용됩니다.
이 재귀 용법을 사용하면 while문이나 for문을 연속해서 사용하지 않아도 되기 때문에 코드가 간결해진다는 것과 변수 사용을 줄여주는 장점이 존재합니다.
변수 사용을 줄이게되면, Side Effect가 발생할 가능성도 줄기 때문에 결과적으로 프로그램에 오류가 생길 가능성이 줄어들고, 프로그램이 정상적으로 돌아가는지에 대한 증명이 쉬워집니다.
하지만, 계속 함수를 호출하게 되면서 지역변수나 반환값 등을 모두 Process Stack에 저장해야합니다. 그리고 이런 과정은 선언한 변수의 값만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게 되고, 이는 속도 저하로 이어집니다.
저는 이런 재귀 용법이 익숙치 않았고 굉장히 어려웠습니다.
그때, 그룹원 분들이 재귀 용법에 익숙해지기 위해 백준에서 N과 M 시리즈라는 알고리즘 문제를 추천해 주셨습니다.
N과 M 문제 자체는 되게 심플했습니다.
N개의 원소들이 저장된 자료구조에서 M개를 선택하여 만족하는 수열을 구하는 문제입니다.
이 문제를 풀게되면 다양한 재귀 용법을 사용함으로써 재귀에 대해서 이해도가 더 높아질 수 있습니다.
이런 자신감을 가진 상태에서 백준에서 하노이 탑 이동 순서 문제를 풀었습니다.
예전에 하노이 탑 알고리즘에 대해서 공부를 했었는데, 이 문제는 재귀 함수를 사용하기에 좋은 문제라고 생각했었습니다.
하지만 이 문제를 풀지 못했는데, 예전에 흘려들었듯이 공부했던 거라 푸는 방식을 계속 생각해려고 노력했지만 도저히 풀지 못하여 다른 사람들이 푼 결과를 참고해서 풀었습니다.
코드 자체는 간단하지만 저는 생각을 못했을 것 같습니다.
이 하노이 탑 문제는 나중에 다시 한 번 풀어봐야지 이해할 수 있을 것 같습니다.
