[TIL] 재귀함수

jay__ss·2021년 12월 5일
1
post-thumbnail

1.재귀함수

어떤 함수가 있고(입력값있고, 출력값있는)
그 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 함수를 의미.

직관적으로, 자신을 계속 불러오며 무한루프에 빠질 수 있기에,
종료조건을 반드시 체크한다.

아래에서는 어느정도의 이해와 암기를 요하는 기본적인 재귀함수를 알아보자.
(재귀함수는 난이도가 있는 편이여서 지금 당장은 외우지 않아도 괜찮다)

1.1 팩토리얼 !

5! = 5 * 4 * 3 * 2 * 1

function factoial(n) {
    if(n <= 1) {  //종료조건을 반드시 체크한다
        return n
    }
    return n * factorial(n-1)
}
// let result = factorial(5);
// console.log(result) -> 120

// 이해를 위한 실행 순서
factorial(5) == 5 * factorial(4) // 5 * 24 -> 120
factorial(4) == 4 * factorial(3) // 4 * 6 -> 24
factorial(3) == 3 * factorial(2) // 3 * 2 -> 6
factorial(2) == 2 * factorial(1) // 2 * 1 -> 2
factorial(1) == 1

1.2 시그마 Σ

n까지의 합을 구하는 문제 (1 + 2 + ... + n)

function sigma(n) {
    if(n <= 1) {
        return n
    }
    return n + sigma(n-1)
}
// let result = sigma(5);
// console.log(result) -> 15
// 이해를 위한 실행순서
sigma(5) == 5 + sigma(4) // 5 + 10 -> 15
sigma(4) == 4 + sigma(3) // 4 + 6 -> 10
sigma(3) == 3 + sigma(2) // 3 + 3 -> 6
sigma(2) == 2 + sigma(1) // 2 + 1 -> 3
sigma(1) == 1

1.3 문자열뒤집기 (역순으로 정렬)

'hello' -> 'olleh'로 뒤집어 버리기!
array.reverse()와 비슷한 느낌. 느낌만!!!

function reverse(text) {
    text += ''  // 어떤 값을 받을지 몰라, 안전하게 문자열을 받겠다는 의지
    if (text.length <= 1) {
        return text
    }
    return reverse(text.slice(1)) + text[0]
}

reverse('hello') == reverse('ello') + 'h'  // == 'olle' + 'h' == 'olleh'
reverse('ello') == reverse('llo') + 'e'  // == 'oll' + 'e' == 'olle'
reverse('llo') == reverse('lo') + 'l'  // == 'ol' + 'l' == 'oll'
reverse('lo') == reverse('o') + 'l'  // == 'o' + 'l' == 'ol'
reverse('o') == 'o'

1.3.1 string의 slice

let str = '123456789'; 
// 숫자가 아니라 문자열이다. 
//순서의 명확성을위해 의도적으로 '123456789'로 선언함.
str.slice(0) // '123456789'
str.slice(1) // '23456789'
str.slice(0, 1) // '1'
str.slice(2, 5) // '345'

1.4 피보나치

// 피보나치
function fibo(n) {
    if(n <= 2) {
        return n
    }
    return fibo(n-1) + fibo(n-2)
}

fibo(4) == fibo(3) + fibo(2) == fibo(2) + fibo(1) + 2 == 2 + 1 + 2 == 5
// 왼쪽
fibo(3) == fibo(2) + fibo(1) == 2 + 1 == 3
fibo(2) == 2
fibo(1) == 1

// 오른쪽 fibo(2)를 다시해야하는 상황

1.5 콤마 찍기

이건 아직 이해가 안간 부분

function comma(text) {
    text += ''
    if(text.length <= 1) {
        return text
    }
    return text.slice(0, 3) + ',' + comma(text.slice(3))
}
profile
😂그냥 직진하는 (예비)개발자

0개의 댓글