개요
재귀적 구조란 자기자신을 정의할 때 자신보다 1차 낮은 부분집합을 사용하고, 또한 그 부분집합은 그보다 차수가 낮은 부분집합을 사용해서 정의하는 과정을 반복하는 구조다. 이러한 구조를 일반적으로 재귀라한다. 재귀를 사용하면 복잡한 알고리즘을 명료하게 기술할 수 있기 때문에 현대 프로그래밍 기법에서 중요한 제어구조의 하나로 여겨진다. 재귀는 프로그램 내에서 일반적으로 다음과 같은 구조를 이룬다. 재귀 호출에는 반드시 탈출 지점이 있어야 한다. 만약 탈출지점이 없다면 재귀 호출은 영원히 계속되고, 컴퓨터의 저장공간 한계로 인하여 스택 오버플로우가 발생하게 된다.
재귀함수 {
탈출조건을 충족 => 함수를 리턴한다.
..... (중간 수행 부분)
재귀호출 => 스스로를 호출한다
}
이떄 재귀함수는 프로그램내에서 스택을 이용하여 호출되게 된다. 먼저 호출된 함수는 프로그램의 수행 순서를 저장하는 부분에 (Stack Register) 차례로 저장되며, 리턴을 하게되면 스택에서 pop하여 수행하게 된다.
예시 1) 팩토리얼의 구현
long factorial(int n) {
if(n == 1)
return n
return factorial(n-1)*n
}
예시 2) 피보나치 수열
long fib(long n) {
if(n == 1 || n == 2)
return 1
return fib(n-1) + fib(n-2)
}
예시 3) 유클리드 호제법 (나머지 함수를 써서 한번에 할 수도 있지만, 좀더 이해를 쉽게 하기 위해)
<syntaxhighlight>
int euclid(int m, int n) {
if(m>n)
return euclid(m-n,n)
if(m < n)
return euclid(n-m.m)
//한방에 euclid(n,m%n) 이렇게 해도 된다.
if(m==n)
return m
}