[재귀] 재귀란? (반복문 vs 재귀 누가더 성능이좋은가!)

.

재귀

 

재귀(Recursion) 란?

: 재귀함수란 자기 자신을 계속 호출하는 함수를 뜻한다.

 

- 자기 자신을 호출할 수 있기 때문에 반복 연산에 자주 사용된다.

- 모든 재귀함수는 무한재귀가 발생하는것을 방지하기 위해 탈출 조건인 기본단계와 재귀단계로 나누어져 있다.

- 함수가 호출될 때 스택 메모리(stack memory)를 사용하게 되는데,

함수의 스택 call이 반복적으로 이루어지므로 메모리를 많이 차지하며 반복문에 비해 성능이 좋지 않다.

- 메모리가 부족한 상황까지 반복된다면 stack overflow가 발생하며 프로그램이 비정상 종료 된다.

 

 

 

재귀 vs 반복문

 

 

 

 

 

여기까지의 결론 

재귀는 반복문보다 느리고 성능이 좋지 않다.

 

 

 

 

그럼 대체 재귀를 왜 사용하는걸까?...

 

 

 

 

 

재귀함수를 사용하는 이유

 

1. 재귀적 표현이 자연스러운 알고리즘일 경우

- 대표적인 예시로 피보나치 수열 점화식이 있다.

*피보나치 수열 점화식 ( f(n) = f(n-1) + f(n-2) )

결과값을 구하기 위해 함수인자만 변경하고 자기 자신을 다시 호출해야 하는 경우이다.

이럴 경우 알고리즘을 기술한 그대로 코드로 표현할 수 있다.

 

 

2. 변수 사용을 줄여준다.

- 변수가 차지하는 메모리에 대한 부분이 아닌 mutable state (변경 가능한 상태)를 제거하여

프로그램 오류가 발생할 수 있는 가능성을 줄일 수 있다.

함수형 프로그래밍에서 함수를 일급객체 취급하여 인자전달 하는것과 비슷한 맥락인듯 하다.

 

 

3. 가독성

2번 특징에 더하여 재귀는 반복문에 비해 코드량이 적다. 때문에 가독성을 향상시키는 코드를 짤 수 있다.

 

 

 

 

 

 

스택오버플로우의 레이캐드웰의 말을 인용하며 마무리 해본다!

 

 

 

 

"프로그램에 반복문을 사용하면 프로그램의 성능을 향상시킬 수 있지만,

재귀를 사용하면 프로그래머의 능력을 향상시킬 수 있다.

상황에 따라 적적한 방법을 골라 사용해라"

 

 

 

 

 

---

 

 

 

참고링크 : https://stackoverflow.com/questions/72209/recursion-or-iteration/72694#72694

Recursion or Iteration?