[알고리즘] 재귀함수

알고리즘 문제를 풀다보면 프랙탈(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. 코드길이

 - 재귀함수를 사용하면 반복문에 비해 코드수를 줄일 수 있다.