[알고리즘/자바스크립트] 트리보나치, 피보나치 수열 "재귀함수"로 구하기 (Fibonacci, Tribonacci Sequence)

[알고리즘/자바스크립트] 트리보나치 수열 구하기 (Tribonacci Sequence)

 

2개월 전에 풀었던 알고리즘 문제를 "재귀함수"를 이용해서 풀어보았다.

지난번에는 위 링크를 보면 알겠지만 

function tribonacci (signature, n) {
	if(n <= 3) {
		return signature.splice(0, n)
	}
	for(var i=0; i<n-3; i++) {
		signature.push(signature[i] + signature[i+1] + signature[i+2])
	}
	return signature
}

이렇게 반복문을 이용해서 풀었다.

초기에 signature라는 배열과 새로 만들어야 할 수열의 길이 수, n이라는 argument가 있다.

 

for문으로 n-3번 반복해서 배열의 i번째, i+1번째, i+2번째 숫자를 더한다.

(n-3인 이유는 초기 배열의 length가 3이라서 n-3번 숫자를 새로 구해서 length가 n이 되도록 해야 하므로)

그래서 push를 하는 방법으로 답을 구했는데

사실 이 문제는 재귀로 풀 수도 있다.

 

 

재귀 호출이란!

함수가 자기 자신을 다시 호출하는 특이한 형태의 함수이다.

가장 대표적인 예시로는 팩토리얼을 구하는 함수가 있다.

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

• 처음에 n에 5가 들어간다.
• 5 != 1이므로 else문으로 간다.
• 5 * 까지 연산한 상태에서 fact(4) 호출.
• 4 != 1이므로 else문으로 간다. 
• 5 *  4 * 인 상태에서 fact(3) 호출
• ... 같은 과정 반복...
• 5 * 4 * 3 * 2 * 에서 fact(1) 호출
• 1 == 1이므로 1 return
• 5 * 4 * 3 * 2 * 1 = 120 return

 

팩토리얼에서 제일 중요한 부분은

무한루프가 되지 않게 해야한다는 것이다.

위 함수에서도 if (n == 1) { return 1 } 이란 부분이 없으면

끝도없이 호출되어서 에러가 날 것이다.

 

 

하여튼 재귀를 이용해서 트리보나치 함수를 구하려니 좀 막막해서

피보나치 수열부터 구해보았다.

 

var i = 0;
function fibonacci (array, n) {
	if(array.length < n) {
		array.push(array[i] + array[++i])
		fibonacci (array, n)
	}
	return array
}

여기서 포인트는 i를 전역함수로 빼서 0이란 값을 준 다음

array[i] + array[++i]를 해준다는 점.

저렇게 하면 +연산보다 먼저 ++연산을 우선적으로 수행하여

i를 1증가시킨 후 array[0] + array[1]을 하고

이 값을 배열에 push하고 그 배열을 다시 자기자신을 호출하면서 파라미터 값으로 던진다.

그러면 새 배열에서 array[1] + array[2]를 수행하고 다시 배열에 push해 줄 것이다.

 

이 과정을 반복하다가 배열의 길이가 n보다 커지면 배열을 return하며 함수를 종료한다.

 

 

function tribonacci (signature, n, i=0) {
	if(signature.length > n) {
		return signature.splice(0, n)
	}
	if(signature.length < n) {
		signature.push(signature[i] + signature[++i] + signature[i+1])
		tribonacci(signature, n, i)
	}
	return signature
}

이제 위의 피보나치 수열을 구하는 재귀함수를 응용해서 트리보나치 수열을 구해보았다.

여기서 포인트는 i를 전역함수로 넣지 않고 함수 argument에 넣었다는 점이다.

그리고 i=0이라고 해주면 기본값이 0으로 세팅된다. (이는 자바스크립트 ES6 문법이다.)

 

signature.length가 n보다 크면 구하고자 하는 수열의 길이가 기존 배열보다 작다는 뜻이다.

그러므로 signature배열에서 0부터 n까지의 배열을 잘라서 return한다.

 

만약에 signature.length가 n과 같다면 if문 어디에도 걸리지 않고 

signature 배열을 그대로 return한다.

 

마지막으로 signature.length가 n보다 작다면 이제 수열을 구할 차례다.

signature[i] + signature[++i] + signature[i+1]을 해줬다.

왜 signature[i] + signature[++i] + signature[++i]가 아닐까?

 

그 이유는 첫번째 연산 시 

signature[0] + signature[1] + signature[2] → 첫번째 i가 0

 

두 번째 연산 시 

signature[1] + signature[2] + signature[3] → 첫번째 i가 1

 

두 번째 연산 시 

signature[2] + signature[3] + signature[4] → 첫번째 i가 2

 

이렇게 i가 1씩 증가해야하기 때문이다.

signature[i] + signature[++i] + signature[++i]

이렇게 쓰면 연산 시마다 i가 2씩 증가하게 된다.