함수의 재귀적 호출의 이해
재귀함수의 기본적인 이해
재귀함수 : 함수내에서 자기 자신을 다시 호출하는 함수를 의미한다.
완료되지 않은 함수를 다시 호출하는것이 가능한가?
⇒ 함수의 복사본을 만들어서 복사본을 실행한다.
재귀 함수는 자기 자신을 계속 호출해서 무한루프를 돌 수가 있다.
따라서 재귀함수에는 재귀의 탈출조건
을 반드시 작성해야 한다.
팩토리얼로 알아보는 재귀 함수
팩토리얼 : 그 수보다 작거나 같은 모든 양의 정수의 곱.
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');
n-1 은 출발지에서 경유지로 갈 것이다 (재귀)
n 은 출발지에서 목적지로 갔다
n-1 은 경유지에서 목적지로 갈 것이다 (재귀)
n을 목적지로 옮기기 위해서는 n-1 개를 경유지로 이동시킨후, n을 목적지로 이동하고 그후에 n-1개를 경유지에서 목적지로 이동시켜야 한다.
일반 재귀함수와 비교해보는 분할정복
탑다운 방식.
주어진 문제를 둘 이상의 부분 문제로 나눈 뒤
각 문제에 대한 답을 재귀 호출
을 이용해 계산 후, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다.
일반적인 재귀 호출은 문제를 한 조각과 나머니 전체로 나누는데, 분할정복은 거의 같은 크기의 부분 문제로 나눈다.
출처
이 글은 윤성우의 열혈 자료구조 라는 책을 회사 동료와 스터디 후 정리한 글입니다.
Author And Source
이 문제에 관하여(함수의 재귀적 호출의 이해), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehaeun0/함수의-재귀적-호출의-이해저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)