Recursion
Recursive Algorithm, Programming, Definition
어떤 일이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(Recursive)이라고 한다. 즉, 자기 호출
을 말한다.
1. 1은 자연수이다.
2. 자연수 n의 바로 다음 수도 자연수이다.
어떤 문제 안에 크기만 다를 뿐, 성격이 똑같은 작은 문제들이 포함되어 있는 것
factorial N! = N * (N-1)!
수열의 점화식
static int factorial(int n) {
if (n>0)
return n* factorial(n-1);
else
return 1;
}
//factorial(3) = 3 * factorial(2)
//-> factorial(2) = 2 * 1
//-> factorial(1) = 1 * 1
int n = 5;
int factorial = 1;
for(int i = n; i >= 1; i--) {
factorial *= i;
}
f(0) = 0, f(1) = 1
f(n) = f(n-2) + f(n-1) (n >=2 일 때 )
static int fiboRecursion(int n) {
if (n < 0) return -1;
if (n <= 1) return n;
return fiboRecursion(n-1) + fiboRecursion(n-2);
// fiboRecursion(3) = fiboRecursion(2) + fiboRecursion(1)
// 1 + 0 + 1
static int fiboIteraion(int n) {
if (n < 0) return -1;
if (n <= 1) return n;
int f0 = 0;
int f1 = 1;
int fn = 0;
for(int i = 2; i <= n; i++) {
fn = f0 + f1;
f1 = f2;
f2 = fn;
}
return fn;
}
재귀를 사용하면 반복문에 비해 간결하고 가독성이 좋은 코드를 작성할 수 있다. 하지만 반복해서 같은 작업을 하기 때문에 반복문보다 성능이나 속도에서 떨어질 수 있다.
재귀는 stack을 사용하기 때문에 쌓이다 보면 stack overflow가 발생할 수 있다. (아직 잘 모르는 부분)
하지만 하드웨어의 발전으로 소프트웨어 자체 성능의 중요도가 낮아졌기 때문에 성능이 중요해서 반복문으로 구현했던 과거와는 달리 가독성을 더 고려하는 부분도 있다고 한다.