JAVA - 자료구조 재귀함수, Recursion

 

# 재귀함수란 ??

 

재귀하다 : 원래의 자리로 되돌아가거나 되돌아오다.  

재귀는 위와 같은 사전적 의미가 있습니다. 

 

이처럼 다시 되돌아오는,

즉 특정 함수에서 자기 자신을 호출하면서 반복하며 문제를 해결합니다.

문제를 해결하기 위해서는 기존 문제에서 더 작은 단위로 쪼개면서 반복을 해줍니다.

 

예를 들어보겠습니다. 10factorial 을 구해봅시다. 

 

f(10 ) = 10 ! 

10factorial, 10!  = 10 * 9 * 8 * 7 * ... * 2 * 1 입니다. 

9factorial, 9! =  9 * 8 * 7 * ... * 2 * 1 입니다. 

그러면 10! 은 10 * 9! 으로 줄일 수 있습니다.

 

이 과정을 반복한다면 

10 ! = 10 * 9!  

10* (9! = 9 * 8!)  

10 * 9 * (8! = 8 * 7!) 

...

...

2! = 2 *1 

이를 함수화 해보면 f(x) = x! = x * (x-1)! 

                                      = x * f(x-1)!   입니다.

이렇게 f(x) = x! 이라는 함수 자기자신을 재호출 해주는 것이 재귀입니다.

 

그러면 간단하게 JAVA로 구현해보겠습니다.

 

1) 

평소에 하던 방법으로 반복문으로 구하면 이렇게 쓸 수 있습니다. 

재귀를 써보겠습니다. 

 

이런 식으로 사용할 수 있겠습니다. 

 

재귀를 사용할 때는 필수적으로 탈출조건이 필요합니다. 

탈출조건이 없을 경우, 무한루프에 빠져 StackOverFlow가 발생합니다.

 

확실히 위의 반복문보다 변수 선언도 없고, 코드도 짧아졌습니다. 

 

재귀함수를 사용하는 이유는

 1) 변수 선언 및 코드를 줄일 수 있습니다. -> 코드가 간결해짐. 

 2) for문이나 while문 등 반복문을 사용 안한다. -> 코드가 간결해짐.

- 코드가 간결해지는 장점이 있다.

장점이 있다면 단점도 있다.

 

단점은 지속적으로 함수를 호출하면서 스택에 저장하게 되고,

값이 크면 클수록 트리구조식으로 가지뻗기를 하면서 메모리를 많이 사용하게 되고,

스택오버플로가 발생하기 때문에 주의해야합니다.

그리고 흐름을 보기가 어렵고, 함수를 호출 후 복귀하는 과정에서  컨텍스트 스위칭 비용이 발생하게 됩니다.

 

 

그러므로 무엇이든 그렇듯이 무조건적으로 좋다곤 할 수 없고,

효율적으로 코드를 짜기 위해선 적재적소에 맞게 사용해야합니다.