재귀함수와 반복문의 차이

재귀함수 (Recursive Function) 란?

 재귀라는 단어는 원래 자리로 되돌아가거나 되돌아옴 을 뜻한다. 프로그래밍에서 재귀는 자기 자신을 호출하는 것을 의미한다. 이러한 재귀의 의미를 사용하여 자기 자신을 다시 호출하여 재참조하는 구조의 함수를 재귀함수라고 한다.

 

재귀함수의 구조

 재귀 함수는 보통 피보나치 수열이나 하노이의 탑 알고리즘에서 많이 사용된다.  이외에도 1 부터 n 까지 숫자의 합이나 팩토리얼 ( ! ) 같은 연산을 할 때에도 사용될 수 있다.

 

재귀함수의 특징

1. 코드의 가독성이 좋다.  2. 스택 메모리를 사용한다.

 

재귀함수와 for 문 (반복문) 의 차이

1. 메모리 

 : 재귀함수는 함수를 반복적으로 호출하기 때문에 스택 메모리를 사용한다. (스택 오버플로우가 발생할 수 있다. )

 반면 반복문은 메모리 힙을 사용한다.

 

2. 코드길이

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

반복문(Iteration) :

• 기본 : 일련의 명령을 반복적으로 실행할 수 있다
• 체재 : 반복에는 초기화, 조건, 루프 내의 명령문 실행 및 제어 변수 업데이트가 포함
• 종료 : 특정 조건에 도달 할 때까지 반복적으로 실행
• 조건 : 반복문의 제어 조건이 참이라면 무한 반복이 발생
• 무한반복 : 무한 루프는 CPU 사이클을 반복적으로 사용
• 스택 메모리 : 스택 메모리를 사용하지 않음
• 속도 : 빠른 실행
• 가독성 : 코드 길이를 더 길게 만들고 변수가 많아 가독성이 떨어짐

재귀함수(Recursion)

• 기본 : 함수 자체를 호출 한다
• 체재 : 기본적으로 종료 조건만 지정 한다 (조건이 추가 될 수도 있음)
• 종료 : 조건부 문은 함수 호출 본문에 포함되어 재귀 호출을 실행하지 않고 함수를 강제로 반환한다
• 조건 : 기본적으로 조건에 수렴하지 않으면 무한 재귀가 발생한다
• 무한반복 : 무한 재귀는 스택 오버플로우를 일으킴
• 스택 메모리 : 스택 메모리는 함수가 호출 될 때마다 새 로컬 변수와 매개 변수 집합을 저장하는데 사용
• 속도 : 느린 실행
• 가독성 : 코드 길이와 변수가 적어 가독성이 높아짐

위의 차이만 본다면 재귀함수와 반복문 중 알고리즘을 작성하는데 있어서는 반복문이 더 낫지않을까 싶다.
재귀 호출이 중요한 이유는 크게 봐서 두 가지 인 것같다.

• 알고리즘 자체가 재귀적인 표현이 자연스러운 경우
• 변수 사용 을 줄일 수 있다.
  변수 사용을 줄여준다는 것은 변수가 잡는 메모리에 대한 이야기가 아니라, mutable state(변경 가능한 상태) 를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄인다는 이야기이다. mutable state 를 최대한 피하는 것은 변수의 수를 줄이는 것과 변수가 가질 수 잇는 값의 종류 또는 범위를 정확히 제한하는 것이라고 생각하면 된다.  점화식을 보면, 결국 f(n)을 구하기 위해선 f(n - 1), f(n - 2)라는 자기자신의 함수를 인자만 바꾸고 다시 호출해야 한다. 이런 경우엔 반복문도 가능하지만, 재귀함수를 이용해서 간단히 구할 수 있다. 대부분 많은 사람들이 이 이유 때문에 재귀함수를 자주 사용 한다.