함수의 재귀적 호출의 이해

이하은·2021년 6월 24일

자료구조 자료구조 스터디 재귀함수 하노이타워

자료구조 스터디

목록 보기

2/2

재귀함수의 기본적인 이해

재귀함수 : 함수내에서 자기 자신을 다시 호출하는 함수를 의미한다.

완료되지 않은 함수를 다시 호출하는것이 가능한가?

⇒ 함수의 복사본을 만들어서 복사본을 실행한다.

재귀 함수는 자기 자신을 계속 호출해서 무한루프를 돌 수가 있다.

따라서 재귀함수에는 재귀의 탈출조건을 반드시 작성해야 한다.

팩토리얼로 알아보는 재귀 함수

팩토리얼 : 그 수보다 작거나 같은 모든 양의 정수의 곱.

ex) 5! = 5 4 3 2 1

수학적으로 0! 과 1! 은 값이 1로 동일하다.

n! = n (n - 1) (n - 2) (n - 3) .... 2 1
n! = n (n - 1)!
n! = n (n - 1) * (n - 2)!
...

위와같이 팩토리얼은 재귀적 특성을 지닌다.

const factorial = (n) => {
	if (n === 0) { // 탈출조건!!
		return 1;
	} else {
		return n * factorial(n - 1);
	}
};

factorial(4); // 24

피보나치로 알아보는 재귀 함수

피보나치 수열 : 앞에 수 두개를 더해서 현재수를 만들어 가는 수열

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

수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값

const fibo = (n) => {
    if (n === 0) return 1; // 탈출조건!!
    if (n === 1) return 1; // 탈출조건!!
    return fibo(n - 2) + fibo(n - 1);
}

console.log('getFibonacci: ', fibo(17)); // 1597

피보나치 함수의 호출 순서

fibo(n - 2) + fibo(n - 1) 여기서 왼편에 있는 함수의 호출이 완료되어야 오른편의 함수호출이 진행된다.

위 사진과 같이 재귀함수의 "호출순서"를 정리하는 것은 매우 복잡하다. 재귀함수 자체를 이해하도록 하자.

위 사진처럼 피보나치 수열의 7번째 값을 구하기 위해서 25회의 함수호출을 한다.

재귀함수(top-down)는 반복문(bottom-up)으로 피보나치의 수를 구할때보다 성능상으로 불리하다. 하지만 코드의 가독성이 좋다는 장점이 있다.

이진 탐색 알고리즘으로 알아보는 재귀 함수

이진 탐색 알고리즘의 탈출 조건 : 탐색 대상을 찾았거나, 탐색 대상이 배열에 존재하지 않거나.

즉 first 가 last 보다 커지는 경우에 해당한다.

const BsearchRecur = (arr, first, last, target) => {
	let mid;
	if (first > last) { // 탈출조건!!
		return -1;
	}

	mid = Math.floor((first + last) / 2);

	if (arr[mid] === target) {
		return mid;
	} else if (target < arr[mid]) {
		return BsearchRecur(arr, first, mid - 1, target);
	} else {
		return BsearchRecur(arr, mid + 1, last, target);
	}
};

const arr = [1, 2, 3, 4, 5, 6, 7, 8];
BsearchRecur(arr, 0, arr.length - 1, -1); // -1

하노이 타워로 알아보는 재귀 함수

const hanoiTowerMove = (n, from, by, to) => {
    if (n === 1) {
        console.log(`${n}번째 탑을 ${from}에서 ${to}로 이동하였습니다.`);
    }
    else {
        hanoiTowerMove(n - 1, from, to ,by);
        console.log(`${n}번째 탑을 ${from}에서 ${to}로 이동하였습니다.`);
        hanoiTowerMove(n - 1, by, from ,to);
    }
};

hanoiTowerMove(3, 'A', 'B', 'C');