재귀 (Recursive)

재귀 함수(Recursive Function)

 함수 내에서 직접 혹은 간접적으로 자기 자신을 반복적으로 호출하는 함수

기저조건(Basis Part)과 유도파트(Inductive Part)로 구성

 - 기저조건(Basis Part) : 재귀 함수 호출이 종료되는 조건

 - 유도파트(Inductice Part) : 동일한 형태의 자기자신을 호출하되 더 작은 해를 반환하는 재귀문을 호출하는 파트

프로그램 메모리 구조에서 스택을 이용하며, 재귀의 Depth가 너무 깊으면 스택 오버 플로우가 발생하게 되므로 기저조건을 잘 판단해야 한다.

 

반복(Iteration) VS 재귀(Recursion)

 반복과 재귀는 유사한 작업을 수행한다.

그래서 반복문으로 구현된 코드의 대부분은 재귀문으로 변환할 수 있으며 반대로 재귀문으로 구현된 코드 역시 대부분 반복문으로 변환할 수 있다.

그러나 더 효율적인 코드를 구현하기 위해 해결할 문제를 고려하여 반복문과 재귀문의 방법을 사용하는 것이 좋다.

먼저, 반복문과 재귀문의 차이점을 알아보자.

 

	재귀문	반복문
수행 시간	느림	빠름
종료	기저 조건(Basis Part)에 의해 종료	반복문의 종료 조건에 의해 종료
메모리 공간	많이 사용	적게 사용
소스 코드 길이	짧고 간결하다	길다
소스 코드 형태	선택 구조(if...else)	반복구조(for, while)
무한 반복	스택 오버 플로우	CPU를 반복해서 점유

프로그래밍을 할 때 재귀보다 반복문이 편할 수 있지만 반복문의 내용이 복잡해지고 변수 상태를 관리하는 것이 오히려 더 복잡해지면 재귀로 구현하는 것이 코드가 더 간단하고 가독성이 좋아질 수 있다.

그러나 만약 입력값N이 크다면 오히려 재귀 알고리즘은 반복문에 비해 비효율적일 수 있으므로 단순한 코드이거나 입력값 N이 작다면 반복문을 사용하는 것이 효율적이다.