Recursive Function

내승현·2022년 4월 24일

recursive function 재귀함수

재귀함수

함수가 자신을 다시 호출하는 구조로 만들어진 함수이다. 재귀함수는 종료조건이 있어야 하며, 종료조건을 설정해주지 않으면 무한 반복을 하게된다. 재귀함수로 작성이 되는 코드는 반복문으로도 작성할 수 있다.

1부터 100의 합 구하기

반복문
let s = 0;
for (var i = 1; i < 101; i++) {
s += i
};
console.log(s); // 5050

수학공식?

알고리즘 문제를 풀기전에 해당하는 수학공식이 있는지 찾아보는 것이 좋다.

let n = 100;
console.log((n*(n+1)/2)); //5050

재귀함수

function f(n) {
    if (n <= 1) {
       return 1 // 종료 조건
    }
    return n + f(n-1) // 재귀함수
}
console.log(f(100)) //5050
// 재귀함수
// 순번   f(n)   n      return       최종
// 1   f(100)  100  100 + f(99)  100+99+98+97+96+95+94..+2+1   
// 2   f(99)   99   99 + f(98)   99+98+97+96+95+94..+2+1 
// 3   f(98)   98   98 + f(97)   98+97+96+95+94..+2+1 
// 4   f(97)   97   97 + f(96)   97+96+95+94..+2+1 
// ...
// 2   f(2)    2    2 + f(1)    2+1
// 1  f(1)    1    1 // return값이 자기 자신을 호출하지 않는 상황

여기서 사용된 for문 조건은 1부터 순회한다. 재귀함수의 경우는 100부터 순회한 다음 호출 스택에 쌓여 있는 값을 처리해 나가게 되는데 스택은 LIFO방식이기 때문에 이때 스택에 제일 마지막으로 반환된 1부터 100까지 순차적으로 더해서 값을 반환하게 된다. 곱하기 방식도 위와 같다.

2진수 변환하기

반복문

let result = '';
let x = 11
while (true) {
    if (x%2 == 0) {
        result += '0'; // result = '0' + result;
    } else {
        result += '1'; // result = '1' + result;
    }
    x = Math.floor(x / 2 );
    // Math.ceil() : 소수점 올림
    // Math.floor() : 소수점 버림
    // Math.round() : 소수점 반올림
    if (x == 1 || x == 0) {
        result += String(x); //result = String(x) + result;
        break;
    }
}
console.log(result.split('').reverse().join('')); //1011

재귀함수

function binary(num) {
    if (num == 1 || num == 0) {
        return String(num) //종료조건
    }
    return binary(Math.floor(num/2)) + String(num % 2)
}
console.log(binary(11)); // 1011
// binary(숫자)  binary(Math.floor(num/2)) + String(num % 2)
// binary(11)  binary(11/2) + String(11%2) \ 101 + String(1) -> 1011  
// binary(5)   binary(5/2) + String(5%2) \ 10 + String(1) -> 101
// binary(2)   binary(2/2) + String(2%2) \ 1 + String(0) -> 10
// binary(1)   1 // if문 조건에 해당
// 더하는 순서에 따라 값이 달라질 수 있다.

숫자와 문자열 더하기는 문자열이 우선시 된다. 그래서 위와 같이 더하게 되면 문자열이 연결된다.

문자열 뒤집기

반복문

let result = '';
let x = 'bakjeongin'
while (true) {
    if (x.length == 1) {
        result += x;
        // 더하는 순서에 따라 순차적으로 반환하거나 거꾸로 반환한다.
        break;
    } 
    let y = x.split(''); // 배열로 만들어 준다.
    result += String(y.pop()); 
    x = y.join(''); // 마지막값을 제외하고 문자열로 변환 되서 x로 들어감
}
console.log(result); //nignoejkab
재귀함수
function strReverse(str) {
    if (str.length == 1) {
        return str //종료 조건
    }
    return str[str.length-1] + strReverse(str.slice(0, str.length-1)); // 순서 더하는 순서 바꾸면 정순
}
console.log(strReverse('bakjeongin')); //nignoejkab

// strReverse(str)          str[str.length-1] + strReverse(str.slice(0, str.length-1)
// strReverse('bakjeongin') str[9] + strReverse(str.slice(0, 9) / 'n' + 'ignoejkab' -> nignoejkab
// strReverse('bakjeongi') str[8] + strReverse(str.slice(0, 8) / 'i' + 'gnoejkab' -> ignoejkab
// strReverse('bakjeong') str[7] + strReverse(str.slice(0, 7) / 'g' + 'noejkab' -> gnoejkab
// strReverse('bakjeon') str[6] + strReverse(str.slice(0, 6) / 'n' + 'oejkab' -> noejkab
// strReverse('bakjeo') str[5] + strReverse(str.slice(0, 5) / 'o' + 'ejkab' -> oejkab
// strReverse('bakje') str[4] + strReverse(str.slice(0, 4) / 'e' + 'jkab' -> ejkab
// strReverse('bakj') str[3] + strReverse(str.slice(0, 3) / 'j' + 'kab' -> jkab
// strReverse('bak') str[2] + strReverse(str.slice(0, 2) / 'k' + 'ab' -> kab
// strReverse('ba') str[1] + strReverse(str.slice(0, 1) / 'a' + 'b' -> ab 
// strReverse('b') str[0] + strReverse(str.slice(0, 0) / 'b'

각 자릿수의 합

반복문

let result = 0;
let x = '123123'
while (true) {
    if (x.length == 1) {
        result += parseInt(x,10);
        break;
    } 
    let y = x.split(''); 
    result += parseInt(y.pop(), 10);
    x = y.join('');
}
console.log(result);
재귀함수
function digitSum(str) {
    if (str.length == 1) {
        return parseInt(str, 10)
    }
    console.log(str.slice(0, str.length-1));
    return parseInt(str[str.length-1], 10) + digitSum(str.slice(0, str.length-1)); // 순서 더하는 순서 바꾸면 정순
}
console.log(digitSum('1231233'));
// digitSum(str)       parseInt(str[str.length-1],10) + digitSum(str.slice(0, str.length-1)
// digitSum('1231233') parseInt(str[6],10) + digitSum(str.slice(0, 9) / 3 + 12 -> 15
// digitSum('123123') parseInt(str[5],10) + digitSum(str.slice(0, 8) / 3 + 9 -> 12
// digitSum('12312') parseInt(str[4],10) + digitSum(str.slice(0, 7) / 2 + 7 -> 9
// digitSum('1231') parseInt(str[3],10) + digitSum(str.slice(0, 6) / 1 + 6 -> 7
// digitSum('123') parseInt(str[2],10) + digitSum(str.slice(0, 5) / 3 + 3 -> 6
// digitSum('12') parseInt(str[1],10) + digitSum(str.slice(0, 4) / 2 + 1 -> 3
// digitSum('1') parseInt(str[0],10) + digitSum(str.slice(0, 3) / 1 -> 1

피보나치 순열

반복문

let a = 1;
let b = 1;
for (var i = 0; i < 6; i++) {
    let c = a + b;
    a = b;
    b = c;
}
console.log(b); // 21
function 피보나치(숫자) {
    if (숫자 == 1 || 숫자 == 2) {
        return 1
    } 
    return 피보나치(숫자-1) + 피보나치(숫자-2)
}
console.log(피보나치(7))
// 피보나치(5) 피보나치(4) + 피보나치(3) -> 3+2
// 피보나치(4) 피보나치(3) + 피보나치(2) -> 2+1
// 피보나치(3) 피보나치(2) + 피보나치(1) -> 1+1
// 피보나치(2) -> 1
// 피보나치(1) -> 1
// f(f(f(f(2) + f(1)) + f(2)) + f(f(2) + f(1)))
// 재귀로 하였을 때 효율이 떨어짐 f(2)를 계속해서 더하고 있다.