재귀 알고리즘과 반복 알고리즘

반복 알고리즘(loop algorithm)

---

 반복 알고리즘(loop algorithm)이란 for, while과 같은 반복문을 이용하여 문제를 해결하는 알고리즘을 말한다. 반복문을 이용한 알고리즘으로는 1부터 100까지 더하는 합 알고리즘이 있다. 

 

재귀 알고리즘(recursive algorithm)

---

 함수는 자기 자신을 내부에서 호출할 수 있다. 이러한 함수를 재귀 함수라고 한다. 재귀 알고리즘(recursive algorithm)이란 재귀 함수를 이용하여 문제를 해결하는 알고리즘을 말한다. 재귀 알고리즘은 팩토리얼이나 피보나치 수열등에 쓰인다.

 

재귀 함수와 반복문의 차이

---

 재귀 함수와 반복문은 속도나 작동 방식에서 차이가 난다. 반복문은 프로그래머가 지정해준 초기값, 조건값, 증감값을 통해 반복을 제어하고 재귀 함수는 함수가 수렴하거나 조건문을 통해 재귀 호출을 종료하는 방식으로 반복을 제어할 수 있다. 반복문은 반복 횟수를 계산하기 편하고 재귀 함수보다 속도가 빠르다. 재귀 함수는 반복 횟수를 알기 어렵고 재귀 함수 특성상 스택의 오버플로우를 발생시킬 수 있다는 문제와 반복문에 비해 속도가 느리다는 단점을 갖지고 있다. 그렇다면 왜 재귀 함수를 계속해서 사용하는 것일까?

 

 재귀 함수는 문제 자체가 재귀적인 경우에 사용한다. 재귀적인 문제란 팩토리얼, 피보나치같이 한 부분이 전체와 같은 형태를 띄는 문제들을 말한다. 팩토리얼을 예로 들면 n! = n*(n-1)!, (n-1)! = (n-1)(n-2)!과 같은 형태를 반복하게 된다. 이런 문제를 해결할 때 재귀 함수를 이용하면 가독성이 높아진다. 물론 속도면에서는 for문을 이용하는 것이 좋지만 문제가 복잡해지면 for의 가독성이 떨어지기 때문에 이 부분은 프로그래머가 잘 선택하여 작성해야 한다.