Recursive Function.

'하노이의 탑' 알고리즘에서 재귀함수란 것을 접해보고, 그 후론 거의 사용할 일이 없었는데....

Functional Language들을 살펴보다보니 재귀 알고리즘에 보다 관심이 생겨난다.

특히, 일반적인 재귀보다 Tail Recursion을 유심히....

아래 예제는 정수 n을 입력인자로하여 1부터 n까지의 합을 구하는 로직이다.

먼저, 일반적인 재귀함수는 대강 이렇게 생겨먹었다.

int sum(int n)

{

    if(n == 1) return 1;

    return (n + sum(n-1));

}

이번에는 Tail Recursion으로 구현해본다.

int sum(int n)

{

    return sum_tail_recursion(n, 0);

}

int sum_tail_recursion(int n, int acc)

{

    if(n == 0) return acc;

    return sum_tail_recursion(n-1, n+acc);

}

코드 길이 따위에 관심을 가질것이 아니라, "함수 호출"에 의한 스택 메모리 사용에 관심을 가져야하겠다.

첫번째 코드상에서 return ( n + sum(n-1) );을 보면

sum(n-1)이 리턴된 후에 다시 n과 더해지기 위해서 스택메모리에 정보가 계속 누적되는것을 알수있다.

반면에 Tail Recursion을 적용했을때는 그럴필요가 없어진다.

정수 n을 충~~~분히 크게 한다면 그 차이가 극명하게 드러난다.

좀 똑똑한 컴파일러라면 Tail Recursion으로 구현된 재귀함수를 반복루프로 바꿔버린다.(어셈블리 언어로 보면 신기하게도 같게 나온다)

물론 최적화 옵션을 줬을때 얘기지만....

(사용하는 컴파일러에서 해당부분을 꼭 살펴봐야한다. 하위버전에서 지원되던것이 상위버전에서 사라지는 경우도 분명 있으니까.. )

--- ...