CWN(CHANGE WITH NEWS) - 알고 나면 유용한 알고리즘 정보...#1. 재귀 함수

재귀는 주어진 문제를 해결하기 위하여 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식을 말한다. 즉, 재귀 함수는 자기 자신을 다시 호출하는 함수이다.

재귀 함수의 간단한 예시로 1부터 n까지 양의 정수를 차례로 곱한 값인 팩토리얼을 언급할 수 있다. 아래의 코드를 살펴보자.

위의 코드는 n부터 1씩 감소하면서 재귀 함수를 호출하고, n이 1이 되었을 때 재귀 함수 호출을 중단하는 코드이다. 이때, 재귀 함수의 호출을 중단하는 종료 조건은 n이 1인 경우이다. 종료 조건을 제대로 명시하지 않으면 함수가 계속 호출되므로 주의해야한다.

재귀 함수의 호출을 중단하면 차례로 결괏값을 자신을 부른 함수에 반환한다. 이를 반환값이라고 한다. 위 코드를 보면 n이 1이 아닐 때, return n*factorial(n-1)를 반환한다는 것을 알 수 있을 것이다. 따라서 자신이 부른 함수 factorial(n-1)이 종료되기 이전에는 계산 결과를 알 수 없다.

이번에는 factorial(4)를 호출한다고 가정해보자. n이 1이 아니므로 4*factorial(3)을 호출하게 된다. 이어, 3*factorial(2)를 호출하며, 그다음으로 2*factorial(1)을 호출한다. 그리고, factorial(1)을 호출하며 종료될 것이다. 이제 n이 1이 되었으므로 factorial(1)은 1을 반환하고, 그 뒤에 2*1을 하여 2를 반환한다. 다시 3*2를 하여 6을 반환하고, 6*4를 하여 24를 반환하면서 종료될 것이다.

모든 재귀 함수는 반복문으로도 구현할 수 있다. 그러나 반복문보다 느리면서 메모리를 많이 차지한다는 단점이 있다.

그런데도 재귀 함수를 사용하는 이유는 무엇일까? 재귀 함수를 사용하면 복잡한 알고리즘을 간결하게 작성할 수 있으며, 변수 사용을 줄여주며 이는 프로그램의 오류 발생할 가능성을 줄인다는 장점이 있기 때문이다.

반복문보다 재귀함수로 구현하기 좋은 예시로는 무엇이 있을까? 그 대표적인 예시는 아래와 같다.

▲ 배열의 합을 구할 때
▲ 등차수열의 합을 구할 때
▲ 피보나치 수열을 구할 때
▲ 하노이 타워 문제를 해결할 때
▲ 순차탐색을 할 때
▲ 이전 단계의 결과를 다음 단계에서 사용할 때

[저작권자ⓒ CWN(CHANGE WITH NEWS). 무단전재-재배포 금지]