Algorithm 문제를 풀때 보통 while이나 for문 같은 반복문을 이용해 문제를 풀곤 했다.
하지만 반복문 만으로는 풀기 어려운 문제들이나, 재귀 함수로 푸는 것이 더 빠르게 접근 가능한 문제들의 경우(DFS, DP, Combination 등) 재귀 함수를 사용하여 문제를 접근하였다.
문제를 풀 때 별 생각없이 반복문으로 푸는게 먼저 생각나면 반복문을 이용하고, 재귀 함수를 이용해 푸는게 생각나면 재귀 함수로 풀곤했는데, 둘의 장, 단점이나 성능적 측면은 생각해본적이 없었던 것 같다.
오늘은 재귀(Recursion)와 반복문(Iteration)에 대해서 알아보려한다.
재귀(Recursion)와 반복문(Iteration)
재귀 함수를 간단하게 설명하자면 자기 자신을 계속 호출하는 함수를 재귀 함수라고 말한다.
반복문과 재귀를 비교해보면 아래와 같다.
반복문 VS 재귀
| 반복문 | 재귀함수 | |
|---|---|---|
| 기본 | 명령을 반복적으로 실행 | 함수 자체를 호출 |
| 체재 | 초기화, 조건, 루프 내 명령문 실행과 제어 변수 업데이트 포함 | 종료 조건만 지정(조건이 추가될 수 도 있음) |
| 종료 | 설정한 조건에 도달 할 때까지 반복 실행 | 함수 호출 본문에 조건부가 포함, 재귀를 호출하지 않고 함수를 강제 반환 |
| 조건 | 제어 조건이 참이라면 무한 반복 발생 | 조건에 수렴하지 않을 경우 무한 재귀 발생 |
| 무한 반복 | 무한 루프는 CPU 사이클을 반복적으로 사용 | 무한 재귀는 스택 오버플로우 발생 |
| 스택 메모리 | 스택 메모리를 사용하지 않음 | 함수가 호출 될 때마다 새 로컬 변수와 매개 변수 집합, 함수 호출 위치를 저장하는데 사용 |
| 속도 | 빠른 실행 | 느린 실행 |
| 가독성 | 코드 길이가 길어지고 변수가 많아져 가독성이 떨어짐 | 코드 길이와 변수가 적어 가독성이 높아짐 |
재귀 함수를 사용하는 이유
재귀 함수를 따지고 보면 반복문보다 좋은 점이 없어 보인다.
재귀 함수는 stack이라는 메모리 공간을 사용하는데, 반복적으로 자기 자신을 부르면서 stack에 계속해서 자기 자신이 쌓여가기 때문에 성능이 좋지 않다.
재귀함수는 stack이라는 메모리 공간을 계속해서 이용하기 때문에 무한 재귀가 발생할 경우 메모리의 제한이 있는 한 stack overflow가 뜨면서 프로그램이 비정상 종료된다.
반복문의 경우엔 stack 메모리를 이런식으로 사용하지 않아 프로그램이 종료되지 않고 무한 실행된다.
재귀 함수를 사용하는 많은 사람들 역시 재귀함수가 반복문보다 느리다는 것을 이미 다 알고 있다.
그럼에도 불구하고 재귀함수를 사용하는 이유는 무엇일까?
1. 알고리즘 자체가 재귀적인 표현이 자연스러운 경우에 재귀함수를 쓰는 것이 유용하다.
[EX] 피보나치 수열 점화식( f(n) = f(n - 1) + f(n - 2) )
위 점화식을 보면, 결국 f(n)을 구하기 위해선 f(n - 1), f(n - 2)라는 자기자신의 함수를 인자만 바꾸고 다시 호출해야 한다.
이런 경우엔 반복문도 가능하지만, 재귀함수를 이용해서 간단히 구할 수 있다.
대부분 많은 사람들이 이 이유 때문에 재귀함수를 자주 사용 한다.
2. 변수 사용을 줄여줄 수 있다.
변수 사용이 줄어든다는 것은, 결과적으로 프로그램에 오류가 생길 가능성이 줄어들고, 프로그램이 정상적으로 돌아가는지에 대한 증명이 쉬워진다.
mutable state를 줄일 수 있다
즉, 사이드 이펙트(side effect)가 없다.
함수형 언어의 특징 중 하나
직관적이지 않은 재귀 호출이 이해하기 어려울 수도 있다.
하지만 프로그램이 복잡해지만 변수가 변하는 상황들을 가능한 피하는 것이 오류 없는 프로그램을 짜는 데에 중요한 사항이 된다.
3. 가독성이 향상된다.
반복문에 비해서 재귀 함수는 코드 가독성 측면에서 코드량이 줄어들고 사용하는 변수가 줄어들어 가독성이 향상된다.
성능만 본다면 반복문에 비해 메모리나 속도 등 성능적 측면에서 많이 뒤쳐져 재귀함수는 사용하지 않는게 맞다.
하지만 H/W가 좋지 못해 S/W 속도를 극한까지 끌어올려야 하는 시대가 아니기에 협업하는 상황을 생각하면 가독성도 고려해 프로그래밍을 해야하기 때문에 프로그램의 목적을 고려하여 재귀 함수를 사용하는 것이 올바르다.
재귀로 구현하면 간단한 코드가 반복문으로 구현하면 매우 복잡해 지는 경우가 많다
재귀와 꼬리 재귀(Recursion And Tail Recursion)
함수를 호출하면 함수가 호출된 위치를 가리키는 주소 값이 저장되어야 한다.
함수가 재귀적으로 호출될 경우 함수 안에서 함수가 계속해서 호출되고 차례로 리턴된다.
그래서 호출 횟수가 많아지면 돌아갈 곳의 주소 값을 저장하고 있는 스택이 넘치거나 프로그램의 실행 속도가 느려지는 단점이 있다.
위의 문제는 함수가 호출된 위치를 기억하기 때문에 발생한다.
이를 위해서 꼬리 재귀가 사용된다.
꼬리 재귀는 재귀 함수를 원래 함수의 꼬리 부분에서 호출하는 경우를 말하는데 컴파일러는 꼬리 재귀로 작성된 코드를 인식해서 반복문으로 바꿔준다.
코드 상에서 해결되는 건 아니고 컴파일러가 꼬리 재귀를 인식하고 코드를 최적화 하면서 일반 재귀가 가지는 단점을 없애준다.
꼬리 재귀는 함수가 호출된 위치로 돌아갔을 때 실행할 작업을 없애 함수 호출 위치를 저장하지 않도록하여 스택이 넘치는 경우를 방지한다.
꼬리 재귀 구현 부분이 일반 재귀랑 같게 실행이 될 수있는데 , 컴파일 옵션에서 코드 최적화가 되도록 설정해 주어야 한다.
꼬리 재귀는 결국 반복문 실행이기 때문에 일반 재귀 함수에서 발생하는 스택 오버 플로우나 성능저하가 발생하지 않는다.
재귀 모습을 한 반복문이기에 가독성과 성능 모두 만족
반복문, 재귀, 꼬리 재귀의 예시는 아래와 같다.
// 반복문
int sum = 0;
for (int i = 0; i <= 100; i++) {
sum += i;
}
////////////////////////////////////////////////////
// 재귀
int sum(int x) {
if(x == 100) return x;
else return x + sum(x + 1);
}
////////////////////////////////////////////////////
// 꼬리 재귀
int sum(int x, int acc) {
if (x>100) return acc;
else return sum(x + 1, x + acc);
}재귀와 꼬리재귀를 비교해보면, return에서 연산이 이루어지는지 함수의 매개변수 안에서 연산이 일어지는지의 차이가 있다.
🙆♂️ 참고사이트 🙇♂️
