recursion (재귀함수)

 

정의

: The act of a function calling itself, recursion is used to solve problems that contain smaller sub-problems. A recursive function can receive two inputs: a base case (ends recursion) or a recursive case (resumes recursion).

-> 함수 자기 자신을 호출하는 행위.

 

예제로 살펴보는 것이 빠를 것이다.

 

 

예시 1 : 팩토리얼(!)

대표적인 예제로 팩토리얼(!)이 있다.

먼저 수학에서 팩토리얼이 어떻게 작동하는지를 알아보자.

5! 의 결과는?
5부터 1사이에 있는 모든 숫자들을 곱한 결과이다.
즉, 5 * 4 * 3 * 2 * 1
그래서 값은 120이 된다.

이 예제를 봤을 때, 뭔가를 발견할 수 있다!

5 * 4 * 3 * 2 * 1 은 결국 5 * 4! 과 같다는 것!

 

그렇다면 여기서 재귀를 활용할 수 있을 것이다.

바로 이렇게!

function factorial(n){
	return n * factorial(n-1)
}
//이 예제는 미완성입니다.

 

그런데 여기서 문제는 이 함수가 끝 없이 호출될 것이라는 점이다.

그렇기 때문에 재귀에서는 꼭 필요한 것이 있다!

 

바로 탈출을 위한 조건이다.

 

팩토리얼의 경우? 임의의 숫자 n 부터 1까지 곱해주는 것이기 때문에 n이 0이거나 0보다 작을 경우에는 호출을 멈추어주어야한다.

그래서 이 때 조건은 n이 0인 경우가 될 것이다!

 

function factorial(n){

	// n이 0일 경우? 1을 리턴하라
	if(n === 0){
    	return 1
    }
    // n이 음수일 경우? undefined를 리턴하라
    if(n < 0){
    	return undefined
    }
    
    return n * fac(n-1)
}

이렇게 재귀함수를 활용한 팩토리얼 함수 만들기가 완성이 되었다!

 

물론 반복문을 통해서 구현할 수도 있지만 경우에 따라서 반복문보다 재귀함수가 효율적인 경우가 있기 때문에 꼭 알아두어야 할 개념이다!

 

 

---

결국 재귀함수의 기본 조건을 정리하자면

출처 : https://velog.io/@jakeseo_me

종료 조건

간단하게, if(나쁜 값이 들어왔다면) { 정지! };과 같이 이해하시면 됩니다. 종료 조건은 재귀의 안전장치입니다. 종료 조건을 여러분들의 긴급 브레이크처럼 생각하세요. 좋지 않은 입력 값이 들어왔을 때, 재귀가 계속하여 동작하는 것을 방지해줍니다.

위의 팩토리얼 예제에서, if (x < 0) return;은 우리가 설정한 종료 조건입니다. 음수의 팩토리얼을 구하는 것은 불가능합니다. 그래서 우리는 음수 입력 값이 들어왔을 때, 팩토리얼 함수가 작동하지 않길 원합니다.

 

기반 조건(Base case, 기저 상태)

간단하게, if(이런 일이 일어난다면) { 성공! }과 같이 이해하시면 됩니다. 재귀의 종료조건과 비슷합니다. 하지만 종료 조건은 모든 나쁜 데이터들을 잡아낸 다는 것을 기억하세요. 반면에 기반 조건은 재귀 함수의 목적 입니다. 기반 조건은 주로 if 문 내부에 있습니다.

팩토리얼 예제에서는, if (x === 0) return 1;이 기반 조건이었습니다. x가 0까지 내려갔을 때, 우리는 팩토리얼을 구하는데 성공한 것입니다!

 

** 재귀

간단하게, 함수가 자기 자신을 호출하는 것입니다.

팩토리얼 예제에서, return x * factorial(x -1);부분이 실제로 재귀가 일어나는 곳입니다. 우리는 숫자 x가 factorial(x-1)함수의 결과 값으로 곱해진 어떤 값을 반환합니다.

 

 

재귀함수의 장점은?

가독성이 좋다!

 

단점은?

호출마다 새로운 call stack을 생성하므로, 메모리를 많이 사용한다!

종료 조건이나 기반 조건을 잘 못 사용했을 때 Uncaught RangeError: Maximum call stack size exceeded 라는 에러가 나오는게 바로 이것 때문!

---

예시 2 : 피보나치 수열

팩토리얼 만으로는 재귀함수를 이해하기 부족한 것 같아 대표적인 또 다른 예제인 피보나치 수열을 재귀함수로 구현해보았다.

 

먼저 피보나치 수열이란?

다음과 같은 점화식으로 정의될 수 있다.

 

즉, 앞의 두 항을 더한 결과가 다음 항이 되는 것이다.

예를 들어

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

이렇게!

 

그럼 피보나치 수열의 n번째 항을 구하는 함수를 재귀함수로 어떻게 구현할 수 있을까?

function fib(n){
	//수열을 보면 0번째 항은 0, 1번째 항은 1이다.
    if(n === 0 || n === 1) {
        return n
    }
	//그리고 1보다 클 경우는 이 재귀함수를 통해 구현한다.
    if(n > 1){
        return fib(n-1) + fib(n-2)
    }
}