[Algorithm - Theory]반복문과 재귀함수의 차이

알고리즘 문제를 풀면서 DFS, DP, Brute Force, Combination 등의 문제를 풀다 보면 간혹 의문이 생긴다. 나는 보통 위와 관련된 알고리즘 문제를 풀 때 재귀함수 를 이용한다. 문제에 따라 달라지긴 하겠지만 반복문, 재귀함수 모두 구현이 가능한것으로 알고있다. 습관적인 부분도 있겠지만 반복문 으로 생각하다가 재귀함수로 바꿔서 푸는 경우도 많았고 그냥 편하다 재귀함수 로 푸는 것이. 왜 그럴까? 반복문 과 재귀함수 의 차이를 알아보자. 

https://wonillism.tistory.com/20

[Programmers - lv02] 피보나치 수 (cpp / python)

피보나치 수를 이용하여 직접 풀어본 포스팅입니다. 이해가 잘 안된다면 참고 하세요.

반복문(Iteration) VS 재귀함수(Recursion)

반복문(Iteration) :

• 기본 : 일련의 명령을 반복적으로 실행할 수 있다
• 체재 : 반복에는 초기화, 조건, 루프 내의 명령문 실행 및 제어 변수 업데이트가 포함
• 종료 : 특정 조건에 도달 할 때까지 반복적으로 실행
• 조건 : 반복문의 제어 조건이 참이라면 무한 반복이 발생
• 무한반복 : 무한 루프는 CPU 사이클을 반복적으로 사용
• 스택 메모리 : 스택 메모리를 사용하지 않음
• 속도 : 빠른 실행
• 가독성 : 코드 길이를 더 길게 만들고 변수가 많아 가독성이 떨어짐

재귀함수(Recursion)

• 기본 : 함수 자체를 호출 한다
• 체재 : 기본적으로 종료 조건만 지정 한다 (조건이 추가 될 수도 있음)
• 종료 : 조건부 문은 함수 호출 본문에 포함되어 재귀 호출을 실행하지 않고 함수를 강제로 반환한다
• 조건 : 기본적으로 조건에 수렴하지 않으면 무한 재귀가 발생한다
• 무한반복 : 무한 재귀는 스택 오버플로우를 일으킴
• 스택 메모리 : 스택 메모리는 함수가 호출 될 때마다 새 로컬 변수와 매개 변수 집합을 저장하는데 사용
• 속도 : 느린 실행
• 가독성 : 코드 길이와 변수가 적어 가독성이 높아짐

위의 차이만 본다면 재귀함수와 반복문 중 알고리즘을 작성하는데 있어서는 반복문이 더 낫지않을까 싶다.
재귀 호출이 중요한 이유는 크게 봐서 두 가지 인 것같다.

• 알고리즘 자체가 재귀적인 표현이 자연스러운 경우
• 변수 사용 을 줄일 수 있다.
  변수 사용을 줄여준다는 것은 변수가 잡는 메모리에 대한 이야기가 아니라, mutable state(변경 가능한 상태) 를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄인다는 이야기이다. 단순한 경우에는 오히려 재귀호출이 직관적으로 이해하기 어려울 수도 있지만, 프로그램이 복잡해지면 mutable state 를 최대한 피하는 것이 오류 없는 프로그램을 짜는 데에 중요한 원칙이 된다.

mutable state 를 최대한 피하는 것은 변수의 수를 줄이는 것과 변수가 가질 수 잇는 값의 종류 또는 범위를 정확히 제한하는 것이라고 생각하면 된다.

아래 두 코드를 보자.
프로그램 1

    int sum = 0;
    for(int i = 0; i <= 100; ++i) {
        sum += i;
    }
    printf("%d\n", sum);

프로그램 2

    int sum(const int x, const int acc) {
    if(x > 100) return acc;
    else return sum(x + 1, x + acc);
    }

    printf("%d\n", sum(0, 0));

둘 다 0부터 100까지의 합을 구하는 프로그램이다.
그런데 프로그램1에는 변수가 두 개 있고, 프로그램2에는 변수가 하나도 없다. (프로그램2에서 x와 acc는 변수가 아님, 값이 바뀔 수 없다.) 그리고 이 경우에는 tail recursion이기 때문에 컴파일러가 똑똑하다면 루프를 사용하는 경우와 동일한 성능을 보장할 수 있고 stack overflow도 없다.

재귀 vs 꼬리 재귀

그렇다면 재귀와 꼬리재귀는 무엇일까?
함수를 호출하면 함수가 호출된 위치를 주소 값이 저장되어야 한다. 함수가 재귀적으로 호출될 경우 함수 안에서 함수가 계속해서 호출되고 차례로 리턴된다. 그래서 호출 횟수가 많아지면 돌아갈 곳의 주소 값을 저장하고 잇는 스택이 넘치거나 프로그램의 실행 속도가 느려진다.

위 문제는 함수가 호출된 위치를 기억하기 때문에 발생한다. 일반적인 재귀 함수의 경우 리턴되는 함수 값을 받아 연산을 하고 다시 그 값을 리턴하는 방식을 취한다. 그렇다면 함수가 호출된 위치로 돌아갔을 때 실행할 작업이 없다면? 함수 호출 위치를 기억할 필요도 없고 스택 오버플로우도 없지 않을까?

꼬리 재귀 가 이 문제를 해결할 수 있는 방법이다. 컴파일러가 꼬리 재귀 최적화 를 지원한다면 성능 및 메모리의 이점을 얻을 수 있다.

int Recursive(int n) 
{
    if(n==1) return 1;
    return n + Recursive(n-1);
}
int Tail_Recursive(int n, int acc)
{
    if(n==1) return acc;
    return Tail_Recursive(n-1, n + acc );
}

일반 재귀는 함수의 마지막, return에 연산이 필요하다. (n + 함수(n-1))
꼬리 재귀는 return에 연산이 필요없다. 매개변수로 필요한 연산을 전달한다. (함수(n-1, n+acc))
여기서부터 꼬리 재귀의 이점은 컴파일러가 지원한다. 컴파일러가 꼬리 재귀를 최적화 할 수 있으면 최적화 하는 과정에서 꼬리 재귀를 반복문으로 변경한다.
따라서 기존 재귀의 문제였던 메모리와 성능에 대한 문제가 제거되는 것이다.

결론

---

성능 측면에서만 본다면 재귀함수는 사용하지 않는 것이 맞다. 반복문으로 구현했을 때 보다 메모리나 속도 등 성능적인 측면에서 많이 뒤쳐지기 때문이다. 하지만 예전처럼 Hardware가 좋지 못해 Software의 속도를 극한까지 끌어올려야 하는 시대가 아니기 때문에 가독성도 고려하여 프로그래밍을 해야한다. 특히 여러사람이 개발에 참여한다면 가독성은 더욱 중요하다. 결국 프로그램의 목적에 맞게 판단해서 사용해야한다.

참조

https://medium.com/sjk5766/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A5%BC-%EC%93%B0%EB%8A%94-%EC%9D%B4%EC%9C%A0-ed7c37d01ee0
https://kldp.org/node/134556