Java | 재귀, 반복, Factorial, Fibonacci

재귀란?

Recursion Recursive Algorithm, Programming, Definition

어떤 일이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(Recursive)이라고 한다. 즉, 자기 호출을 말한다.

1. 1은 자연수이다.
2. 자연수 n의 바로 다음 수도 자연수이다.

재귀적 구조

어떤 문제 안에 크기만 다를 뿐, 성격이 똑같은 작은 문제들이 포함되어 있는 것

factorial N! = N * (N-1)! 수열의 점화식

---

재귀 vs 반복

Factorial

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;
    }
	

Fibonacci

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가 발생할 수 있다. (아직 잘 모르는 부분)
하지만 하드웨어의 발전으로 소프트웨어 자체 성능의 중요도가 낮아졌기 때문에 성능이 중요해서 반복문으로 구현했던 과거와는 달리 가독성을 더 고려하는 부분도 있다고 한다.