재귀와 재귀 그리고 재귀

 재귀를 배웠다.

코틀린으로 처음 프로그래밍을 접하고 클래스까지는 공부를 했었지만 재귀부터는 모르는 상태로 부트캠프를 시작했다. 

재귀란, 사전적 정의로는 아래처럼 정의되어져 있다.

 

재ː귀, 再歸

명사

1. 본디의 곳으로 다시 돌아오는 것.  (정의 출처: Oxford Languages)

Oxford Languages and Google - Korean | Oxford Languages

 과거의 프로그래밍은 하드웨어적인 부분이 지금처럼 발전을 한 상태가 아니었기때문에 조금의 메모리도 최대한 효율적으로 쓰기위한 코딩을 했었다고 한다. 하지만 작금에 와서는 거의 모든 디바이스들의 성능이 미세한 부분정도는 신경쓸 가치가 없을 정도로 발전했기 때문에 과거처럼 너무 메모리 하나하나에 얽메이지 않고 코딩을 할 수 있게 되었다. 이제는 컴퓨터 성능에 대한 부분보다는 개발자본인과 팀원들간의 의사소통을 위해 깔끔하고 잘 정리된 코드가 잘 짜여진 코드라고도 할 수 있겠다. 물론 코드의 재사용성과 같은 다른 부분들도 고려해야할 사항이겠지만 재귀와 관련된 부분에서만 언급을 하겠다. 그래서 재귀라는 개념을 프로그래밍에 접목함으로써 코드가 훨씬 잘 정리가 되었다. 

 

 재귀 알고리즘이란 재귀 함수 스스로의 논리를 반복적으로 사용해 문제를 해결하는 것이다. 이러한 특성 때문에 재귀 알고리즘은 비슷한 방식의 일처리가 반복될 때 사용된다. 가장 대표적인 예로는 피보나치 수열과 팩토리얼이 있다. 

 피보나치 수열은 아래처럼 0과 1로 시작하면서 세번째 부터는 앞의 두 값의 합을 값으로 한다. 

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...... ]

여기에서 재귀의 개념을 살펴보면 몇번째 수가 되었든간에 해당위치의 값은 무조건 해당위치 이전과 그 이전의 숫자의 합이된다. 

다시말하면 N번째 값을 구하기 위해선 N-2의 값과 N-1의 값을 더하면 된다는 말이다. 이러한 논리가 수열 전체에 적용이 되기때문에 피보나치 수열이 재귀 알고리즘의 대표적인 예가 될 수 있다. 왜냐하면 재귀알고리즘은 비슷한 방식의 일처리가 반복될 때 사용되기 때문이다.

 

 이와 더불어 팩토리얼을 알아보면, 한글로는 계승이라고 하며 1부터 시작하여 범위까지의 모든 숫자를 곱하는 것을 말한다. 숫자 N 까지의 팩토리얼을 구한다고 하면 N!이라고 표현된다. 5!이라고 하면 1부터 5까지의 모든 숫자의 곱이 된다. (5*4*3*2*1 = 120) 이것을 작은 부분으로 쪼개서 살펴보면 시작하는 수는 1이 되고 1과 그 다음수, 2를 곱한다. 그리고 나온값에 2의 다음수, 3을 곱하고 이 계산을 마지막으로 곱하는 숫자가 5가 될 때 까지 반복한다. 

 

 아래 코드는 팩토리얼을 반복문으로 풀어 쓴 함수이다.

function iterate(n) {
	let result = 1;
	for (let i = 1; i <= n; i++) {
    	result = result * i;
    }
    return result; 
}

아래코드는 재귀 알고리즘을 이용해 만든 재귀함수이다.

function factorial (n) {
	if (n === 1) {
    	return n;
    }
    return n*factorial(n-1);
}

factorial(5); // 120
-> {
	if (5 === 1) { //5와 1은 같지 않기 때문에 if문 안의 리턴은 실행되지 않고 넘어간다.
    	return n;
    }
    return 5*factorial(5-1); //5-1=4
}			->{
               if (4 === 1) { //역시 4와 1은 같지않기때문에 넘어간다.
                  return n;
               }
               return 4*factorial(4-1); //4-1=3
               }		-> {
                            if (3 === 1) {
                               return n;
                            }
                            return 3*factorial(3-1); //3-1=2
                            }		-> {
                                        if (2 === 1) {
                                           return n;
                                        }
                                        return 2*factorial(2-1); //2-1 = 1
                                        }		-> {
                                                    if (1 === 1) { //1과 1은 같기때문에
                                                      return 1;//if문안의 리턴문이실행된다.
                                                    }
                                                    return n*factorial(n-1);
                                                    }		

//위의 과정을 압축해보면, 
factorial(5);
return 5*factorial(5-1);
	     ->return 4*factorial(4-1);
				   ->return 3*factorial(3-1);
						      ->return 2*factorial(2-1);
									     ->return 1;
//이렇게 나오고 이를 거꾸로 거슬러 올라가며 계산을 하면,
return 5*factorial(5-1);
	     ->return 4*factorial(4-1);
				   ->return 3*factorial(3-1);
						      ->return 2*1;
------------------------------------------------------------
return 5*factorial(5-1);
	     ->return 4*factorial(4-1);
				   ->return 3*2*1;
------------------------------------------------------------
return 5*factorial(5-1);
	     ->return 4*3*2*1;
------------------------------------------------------------
return 5*4*3*2*1;
------------------------------------------------------------
120; //값은 120이 나오게 된다.