알고리즘에서의 재귀적인 방법

재귀(再歸)란?


 
원래 자리로 되돌아오거나 되돌아옴을 뜻하는 명사이다.

처음있던곳으로 계속 돌아온다는 뜻을 가진 이 단어는

프로그래밍에서 재귀용법이라는 알고리즘으로

프로그래머들을 때로는 탄성으로, 때로는 경악으로 몰고가는 알고리즘들 중 하나에 속한다.




재귀적 표현을 프로그래밍으로 그대로 옮겨놓은 것이 재귀함수(recursive function) 인데

이것은 자기자신을 계속적으로 호출하는 함수를 뜻하며 2가지 방법론이 제시된다.

- 함수안에서 자기자신을 직접 호출하는 방법

- 두개의 함수가 상호 호출하는 방법

왠만하면 한큐에 끝낼 수 있는 자기자신을 직접 호출하는 방법이 더 좋다.




재귀용법은 일반적인 프로그래밍에서도 많이 응용이 되는데...

예를들어 지뢰찾기의 어떤 블럭을 클릭했을때 주변에 빈블럭이

있다면 다음 블럭을 계속적으로 검색하며 열어주는 것을 본적이 있을 것이다.

이러한 문제도 재귀적 호출을 사용하면 간단하게 해결이 가능하다.



그 이외에 디렉토리를 검색하는방법, 퀵 소트 , 트리...

여러 곳에서 두루 쓰이는 이 재귀적 용법을 간단한 perl 코드로 살펴보도록 하자.




이 코드는 factorial의 값을 구하는 함수이다. ( 재귀적 용법이 사용되지 않았다.)

예를들어 함수의 인자값으로 5를 넣으면 5 * 4 * 3 * 2 * 1 의 결과인  120이 반환된다.

1 2 3 4 5 6 7 8

sub factorial{ my ($n) = shift; my ($result,$i) = ( 1 , 2); for( ; $i <= $n; $i++){ $result *= $i; } return $result; }

이제 제귀적 용법은 어떤식으로 응용될 수 있는지 살펴보도록 하자.

sub factorial_recursive{ my ($n) = shift; return $n if $n <= 2; return $n * factorial_recursive($n - 1); }

변수 $n이 2보다 같거나 작을때까지

$n을 계속적으로 1씩 감소시키며 자기 자신을 호출하는 예제이다.

위의 코드보다 보기가 훨신 깔끔하고 코드도 줄었다.



여기서 뽀인트!


이 두 서브루틴이 같은 연산을 할때 걸리는 시간은 누가 더 빠를까?

일반적으로 코드도 짧고 깔끔해보이는 재귀함수가 더 빠르다고 생각하지만

실제로는 for문으로 해결한 함수가 훨신 더 빠르다. 



Benchmark 함수로 속도를 비교해보았다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

use Benchmark; timethese(100000,{ not_recurisve => 'factorial(100)', recurisve => 'factorial_recursive(100)'}); sub factorial{ my ($n) = shift; my ($result,$i) = ( 1 , 2); for( ; $i <= $n; $i++){ $result *= $i; } return $result; } sub factorial_recursive{ my ($n) = shift; return $n if $n <= 2; return $n * factorial_recursive($n - 1); }

Output:

1 2 3 4 5 6

Benchmark: timing 100000 iterations of not_recurisve, recurisve... not_recurisve: 3 wallclock secs ( 2.45 usr + 0.00 sys = 2.45 CPU) @ 40766.41/s (n=100000) recurisve: 9 wallclock secs ( 8.70 usr + 0.00 sys = 8.70 CPU) @ 11488.97/s (n=100000)

약.. 4배정도 재귀함수를 쓰지않은 함수가 더 빠른것을 확인 할 수 있다.

이렇게 느려지는 이유는 무엇인가?

어떻게 보면 당연한 이유인데

재귀적으로 함수를 호출하면 계속적으로 스택이 쌓이므로

서브루틴을 호출하고 다시 되돌아오는데 많은 시간을 잡아먹는 것이다. ( 리버싱으로 확인가능 )




오늘의 제안

1. 컴퓨터의 원리를 파고들면 알고리즘적으로 더 빠른 프로그래밍을 할 수 있을 것에 대한 확신

2. 무작정 재귀함수를 사용하려고 하지말고 꼭 써야 할때만 써야한다.