재귀 알고리즘은 많은 분야에서 사용되고 있으며, 특히 복잡한 문제를 해결하는데 유용한 도구 중 하나이다.
트리 구조나, 그래프 탐색 문제와 같은 복잡한 문제를 간단하게 처리할 수 있고, 최근 인공지능 분야에서 이미지 생성 과정에서 중간 결과를 평가하고 수정하는 방식과 같은 재귀적 접근이 많이 사용되고 있다고 한다.
재귀 알고리즘을 알아보기 전에 먼저 재귀란 무엇일까?
재귀 :
재귀란, 반복 호출을 통해 계속해서 문제를 가장 작은 단위까지 쪼개는 것으로, 문제 해결의 한 방식으로 이해할 수 있다.
재귀 알고리즘 :
재귀 알고리즘이란,하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘이다.
재귀는 반복 호출을 통해 계속해서문제를 가장 작은 단위까지 쪼개는 것으로, 문제 해결의 한 방식으로 이해할 수 있다.
더 이상 문제가 쪼개지지 않을 때 까지 함수 자신을 호출하는 과정을 반복한 후 최종값을 반환하게 된다.
재귀함수를 작성할 때는 함수 내에서 다시 자신을 호출한 후 그 함수가 끝날 때 까지 함수 호출 이후의 명령문이 수행되지 않는 다는 사실과 종료조건이 꼭 포함 되어야한다는 부분을 인지하고 작성하면 무한루프를 방지할 수 있다.
재귀는 언제 사용할까?
(1) 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우 (2) 반복문이 많이 중첩되거나 중첩 횟수를 예측하기 어려운 경우 (3) 변수 사용을 줄여 mutable state를 제거해 프로그램 오류가 발생할 가능성을 줄이고자 하는 경우
주의:대부분의 경우 재귀를 활용하면 반복문의 경우보다 코드가 훨씬 간결하다.모든 재귀 알고리즘은 for, while과 같은 반복문으로 표현할 수 있다.
그렇다고 해서 반복문보다 효율적인 것은 아니다. 고로 재귀를 쓸 수 있다고 해서 무조건 재귀를 쓰는 것은 바람직하지 않다.
종결문이 없거나(무한 재귀), 종결문이 절대 참이 될 수 없는 경우, 또는 매우 큰 수를 재귀 함수로 돌린다면 컴퓨터 메모리에 공간이 없을 때까지 계속해서 같은 메서드를 호출 스택에 푸시한다. 이로 인해스택 오버플로라는 오류가 발생한다.
재귀 함수란? :
함수 안에 자신의 함수를 다시 호출하는 함수를 의미한다.
이러한재귀함수는 자신의 로직을 내부적으로 반복하다가, 일정한 조건이 만족되면 함수를 이탈하여 결과를 도출합니다.
재귀 함수의 장점 :
변수를 여럿 만들 필요가 없다. 예를 들어 현재 상태를 저장해야 할 경우 tmp 변수를 만들기보다 상태를 메서드를 재귀적으로 호출하면서 변경된 상태를 전달 함으로써 변수의 수를 줄일 수 있다.
while문이나 for문같은 반복문을 사용하지 않아도 되기에 코드가 간결해진다.
재귀 함수의 단점 :
지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환 값을 모두 콜 스택에 저장해야 한다.
그리고 이런 과정은 임시 변수 (선언한 변수의 값)만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게 되고, 이는 속도 저하로 이어진다.
함수 호출 -> 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 된다.
콜 스택 이란? : 컴퓨터 프로그램에서 현재 실행 중인 서브루틴에 관한 정보를 저장하는 스택 자료구조이다.
콜 스택 이미지 예시
컨텍스트 스위칭이란?
현재 실행 중인 함수의 상태를 저장하고 다른 함수로 이동하는 과정을 말합니다. 이것은 컴퓨터가 코드를 실행하는 동안 함수 간의 전환과 실행 위치를 추적하는 데 사용됩니다. 함수가 호출되면 호출된 함수에 필요한 정보(지역 변수, 매개변수, 반환 주소)를 스택에 저장하고, 호출된 함수가 종료되면 그 함수의 정보를 스택에서 제거하여 이전 함수로 돌아가는 과정을 의미합니다. 이때, 현재 실행 위치, 지역 변수, 매개변수, 반환 주소 등이 스택 프레임에 저장되어 컨텍스트 스위칭이 이루어집니다.
이 작업은 프로그램의 흐름을 유지하고 함수 호출 및 복귀를 관리하는 데 필요하지만, 이 과정에서 오버헤드가 발생할 수 있습니다. 특히, 많은 함수 호출이 발생할 때 이러한 스위칭은 시스템 자원을 사용하며, 이로 인해 성능 저하가 발생할 수 있습니다.
따라서, 재귀 함수 또는 많은 수의 중첩된 함수 호출을 사용하는 경우에는 이러한 문맥 스위칭에 따른 오버헤드를 고려해야 합니다. 종종 반복문이나 다른 방식으로 문제를 해결하는 것이 더 효율적일 수 있습니다.
스택 프레임
main() -> func1() -> func2() -> ...
이렇게 스택 영역에 차례대로 저장되는 함수의 호출 정보를 스택프레임 (Stack frame) 이라고 한다.
함수의 호출과 함께 메모리의 스택 (Stack) 영역에 함수의 호출과 관계되는 지역변수와 매개변수가 저장되는 영역이다.
스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다.
함수가 호출되면 스택에서는
함수의 매개변수,
함수에서 선언된 지역 변수,
호출이 끝난 뒤 돌아갈 반환 주소값 등이 저장된다.
**반환 주소 값 : 함수 호출 이전에 실행되던 코드의 위치
이러한 스택 프레임 덕분에 함수의 호출이 모두 끝난 뒤에, 해당 함수가 호출되기 이전 상태로 되돌아 갈 수 있다.
위에 재귀 함수의 단점에 대해 다루면서
재귀 함수의 가장 큰 문제는 자기 자신을 호출한 뒤 결과를 기다리면서 생기는 콜 스택의 부하로 인한 메모리 낭비였다.
재귀 함수의 단점을 극복할 수 있는 방안에는 무엇이 있을까?
재귀 함수 단점 극복 방안 - 꼬리 재귀 개념의 활용
꼬리 재귀라는 개념을 이용하면 재귀 호출이 끝나는 시점에서 아무 일도 하지 않고 바로 결과를 반환하도록 하는 방법으로 함수의 상태 유지 및 추가 연산을 하지 않기에 스택 오버 플로우 해결할 수 있다.
// Basic Recursion
int factorial(int n, int total) {
if (n === 1) {
return 1;
}
return n * factorial(n-1);
}
// Tail Recursion
int factorial(int n, total) {
if (n === 1) {
return 1;
}
return factorial(n - 1, n * total);
}
차이점을 잘 보면 반환 부분 코드가 달라졌다. 꼬리 재귀의 핵심은 반환부에 연산이 없어야 한다는 점이다.
이렇게 반환부에 연산이 없도록 구현을 한다면 컴파일러는 꼬리 재귀 최적화를 지원하여 자체적으로 재귀 함수를 해석해서 반복문으로 변경해서 실행한다.
재귀 함수의 특성
재귀 함수는특정 입력에 대해서 자기 자신을 호출하지 않고 종료해야 한다.
또한 모든 입력은 base condition으로 수렴 해야만 한다.이를 지키지 않으면 재귀함수는 무한루프에 빠져 에러를 발생시키고 말 것이다.
void recursive(int n){
cout << n << endl;
recursive(n-1);
}
위의 함수는 n부터 1까지의 값을 출력하는 재귀 함수이다. 하지만 recursive 함수를 실행시키면 무한루프에 빠져 프로그램이 뻗고 말 것이다. 그 이유는 Base Condition을 따로 지정해 주지 않았기 때문이다.
void recursiveFixed(int n){
if(n==0) return; // base condition
cout << n << endl;
recursive(n-1);
}
recursiveFixed 함수에 base condition을 추가 해주었다. 특정 입력(0)에 대해서 자기 자신을 호출하지 않고 종료하며, 모든 입력은 base condition으로 수렴하기에 무한루프에 빠지지 않고 정상적으로 n부터 1까지의 수를 출력한다.
함수를 명확하게 정의하자
재귀함수를 만들때는 함수를 명확하게 정의해야 한다. 함수를 명확하게 정의한다는 것은
1. 함수의 인자로 어떤 것을 받을지,
2. 어디까지 계산한 후 자기 자신에게 넘겨줄 지를 명확히 하는 것을 의미한다.
(스택 프레임, 컨텍스트 스위칭 개념과 이어지는 부분이다.)
재귀함수와 반복문
모든 재귀함수는 재귀구조 없이 반복문 만으로 동일 동작을 수행하는 함수를 구현할 수 있다.
재귀를 적절하게 잘 사용하면 코드가 간결해 진다는 장점이 있지만, 메모리와 시간적 측면에서는 어느정도 손해를 보게 된다.
따라서 반복문으로도 간단하게 해결 가능한 문제라면 반복문을 사용해 구현하고, 반복문 만으로는 너무 코드가 복잡해 질 것 같다면 재귀 구조를 사용하는 것이 좋다.
재귀 함수와 반복문과는 어떤 차이점이 있을까?
재귀 함수에서 '자기 자신을 호출한다'는 말이 자기 자신으로 '반복해서 돌아간다'는 의미를 내포하는 것 같다면, 맞다. 모든 재귀 함수는 반복문(while문또는for문)으로 표현할 수 있다. 그렇다면 반복문과 무슨 차이가 있을까?
for(int i = 0; i < arr.length; i++){...}
예시로배열에 들어간 요소의 합을 반복문으로 구한다고 생각해보면, 이런 코드로 구할 수 있을 것이다.
그런데, 배열의 요소로 숫자만 들어있는 게 아니라 배열이 겹겹이 들어있다면 for문 안에 for문을 (필요한 횟수만큼) 넣어야 할 것이다. 계산이 전혀 불가능한 것은 아니나 이렇게 해결할 경우 오류가 나기 쉽고, 코드가 몹시 지저분해질 것이다.
return num + arrSum(num-1);
이럴 때 arrSum이라는 메서드를 만들고, 재귀로 arrSum을 계속 호출하면 반복문을 실행하는 것과 같은 효과를 누리면서 훨씬 간결한 코드를 쓸 수 있다.
