[자료 구조와 알고리즘] 재귀적으로 생각하기

 

 

 

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘

 

재귀적으로 생각하기

 

 

 

 

📍 재귀 함수를 만들 때는 해당 함수가 이미 구현되었다고 생각하면 좋음!

ex) 5! = 5 * factorial(4);

      1~5까지 배열의 합 = 5 + 1~4까지의 배열 합

 

 

 

📍 패턴 1: 단순 반복 실행 

👉🏻 반복문으로 구현했을 때보다 큰 이점이 되는 부분이 없음

👉🏻 오히려 콜 스택 공간을 많이 차지해 성능이 for문보다 좋지 않음

 

 

 

📍 패턴 2: 하위 문제의 결과를 기반으로 현재 문제 계산

👉🏻 ex: facorial

     //상위 문제  // 하위 문제
return number * factorial(number - 1);

👉🏻  for문을 이용해 계산하는 방식을 상향식 계산, 재귀를 이용하여 하위 문제 기반으로 현재 문제 계산하는 방식을 하향식 계산이라고 함

 

👉🏻 재귀를 사용한다고 모두 하향식 계산이 아니라 '하위 문제의 결과를 기반으로 현재 문제를 계산'할 때 하향식 계산이라고 함 

👉🏻 상향식 계산은 for문, 재귀 함수로 모두 구현 가능하나 하향식 계산은 재귀 함수로만 구현 가능함

👉🏻  ex: 1~5까지의 배열의 합을 구하라

[1, 2, 3, 4, 5]

1~4까지 더하는 하위 문제
하위 문제에 5만 더하면 됨

[ sum_of_array.mjs ]

function sumArray(arr) {
    if(arr.length == 1) return arr[0]; // 기저 조건
    return sumArray(arr.slice(0, -1)) + arr[arr.length - 1];
}

let arr = [1, 2, 3, 4, 5];
let sum = sumArray(arr);

console.log(sum);

 

 

📍 (재귀를 하향식으로 사용 예시) 문자열의 길이 구하기

[ length_of_str.mjs ] 

function strLength(arr) {
    // 문자열의 길이 구하기를 재귀적으로 하향 방식으로 푼다면?
    // 하위 문제: 구하려는 문자열의 마지막 원소를 제외한 나머지 부분
    //          + 나머지 문자열 하나를 더해 주기!

    // 기저 조건: 배열에 원소가 없을 때
    if(arr[0] == null) return 0;
    return strLength(arr.slice(0, -1)) + 1;
}

let str = "abcde";
let len = strLength(str);

console.log(len);

 

 

 

 

📍 (재귀를 하향식으로 사용 예시) 지수함수 구하기

👉🏻 지수함수란? 숫자를 몇 제곱 하는 것

👉🏻 ex) 밑이 2이고, 지수가 5라면 2를 5번 곱하라는 뜻 ( 2 * 2 * 2 * 2 * 2)

 

[ power.mjs ]

function power(x, n) {
    // 2의 5승을 구하는 게 문제라면?
    // 하위 문제: 2의 4승 구하기
    //          + 2를 한 번 더 곱해 주면 끝!
    if(n == 0) return 1; // 기저 조건
    return power(x, n-1) * x; // 하위 문제
}

console.log(power(2, 5));