[알고리즘] 재귀함수
알고리즘 문제를 풀다보면 프랙탈(fractal) 과 같이 패턴이 반복되는 구조를 마주칠 때가 있다.
반복되는 구조를 코드로 작성하려면 for 문을 사용하면 되지만 재귀함수를 통해서도 구현할 수 있다.
결국 자신이 원하는 결과를 얻기 위해 올바른 코드를 작성했으면 for 문이든 재귀함수든 결과는 똑같겠지만
그럼에도 불구하고 for문과 재귀함수에 어떤 차이가 있는지 알고 사용하는게 중요하다.
개인적으로는 자신에게 쉽고 빠른 방법을 선택하는게 좋은 것 같다 :)
재귀함수 (Recursive Function) 란?
재귀라는 단어는 원래 자리로 되돌아가거나 되돌아옴 을 뜻한다.
프로그래밍에서 재귀는 자기 자신을 호출하는 것을 의미한다.
이러한 재귀의 의미를 사용하여 자기 자신을 다시 호출하여 재참조하는 구조의 함수를 재귀함수라고 한다.
재귀함수의 구조
재귀 함수는 보통 피보나치 수열이나 하노이의 탑 알고리즘에서 많이 사용된다.
이외에도 1 부터 n 까지 숫자의 합이나 팩토리얼 ( ! ) 같은 연산을 할 때에도 사용될 수 있다.
예를들어 1 부터 n 까지 숫자의 합을 구하는 재귀함수는 아래와 같다.
public int sum(int n){
if(n==0) {
return 0;
}
return n + sum(n-1);
}
int total = sum(10); // 55 ( 1 부터 10까지의 합 )
재귀함수를 살펴보면 return 을 통해 다시 자기자신을 호출하고 있는 걸 볼 수 있다.
그런데 재귀함수를 사용할 때 주의할 점이 있다. 재귀함수가 종료되는 조건을 넣어 줘야한다는 것이다. 그렇지 않으면 재귀함수는 무한루프에 빠지게 된다.
코드에서 보듯이 처음에 if 문을 통해 n 이 0 인지 체크하고 0 이면 0 값을 반환하고 함수를 종료한다.
재귀함수의 특징
1. 코드의 가독성이 좋다.
2. 스택 메모리를 사용한다.
재귀함수와 for 문 (반복문) 의 차이
1. 메모리
: 재귀함수는 함수를 반복적으로 호출하기 때문에 스택 메모리를 사용한다.
(스택 오버플로우가 발생할 수 있다. )
반면 반복문은 메모리 힙을 사용한다.
2. 코드길이
- 재귀함수를 사용하면 반복문에 비해 코드수를 줄일 수 있다.