[자료구조, 알고리즘] 재귀호출 - 헷갈리면 모르는것

[특징 및 이해할 때 필요한 개념]

(1) 재진입 개념이 아닌 복사본 개념 : 스택에 쌓인 함수는 각각의 함수

(2) 반복 : 이전의 연산에 기반해서 현재의 것을 연산할 때 사용 : 함수에서 함수를 호출

=> 동일 패턴 반복

 

(3) 문제 -> 논리 세우기 -> 코드화 / 패턴화(함수, 0 - 1 - ---- - n-1 - n - n+1)

(4) 메모리(코드) - CPU(연산) : 언어 런타임 별 메모리 할당 구조 살펴보기

(5) 함수 호출 관계 - 순서 한번쯤 따져보기

=> 호출한 함수가 모두 끝난 후(return) 되돌아와서 실행

=> 수학의 함수 개념 : 정의역, 공역, 치역(특정 값을 도출해내기위한 패턴)

(6) 성능상 좋지않으나(재귀 두갈래 이상 out of memory 조심) 간결한 코드

[예시]

(1) 팩토리얼 : 이전 연산 결과값에 지금 연산 결과값 도출 - 함수 내에서 함수를 실행(새로운 함수) , 배경지식

function factorial(n){
    if(n === 0){
      return 1;
    } else {
         return n * factorial(n-1);
     }
}

(2) 피보나치 수열 : 이전 연산 결과값 활용, 함수 호출 관계 - 순서

function Fibo(n){
    //함수 호출 순서를 출력하기위한 코드
    console.log('Fibo(' + n + ') 호출');

    if(n===0){
        return 0;
    } else if(n===1){
        return 0;
    } else {
        return Fibo(n-1) + Fibo(n-2);
    }
}

(3) 이진탐색 : 순차탐색하지않고, 범위를 좁혀나가는 방식(start, end, mid, target을 이용)

function binarySearch(arr, start, end, target){
    var mid = parseInt((start+end)/2);

    /* 탐색범위를 벗어났을 때 */   
    if(start > end){
        console.log('탐색이 모두 끝났습니다');
        return -1;
    }


    /* mid 탐색은 이미 했기때문에 할 필요가 없음 */
    if(arr[mid] > target){
        binarySearch(arr, start, mid-1, target);
    } else if(arr[mid] < target) {
    binarySearch(arr, mid+1, end, target);
    } else {
        console.log('target의 위치 : ' + mid);
    }
}

  

(4) 하노이타워 : 패턴화(0, 1, 2, ---, n-1, n), 전의 연산 활용, 반복의 끝(탈출조건), 명목적인 공간(메세지로 출력), 함수 호출관계 - 순서

function Hanoi(num, from, by, to){
    if(num == 1){
        console.log(num +'이 ' + to + '로 이동');
        return ;
    }

    Hanoi(num-1, from, to, by);
    console.log(num + '이 ' + to + '로 이동');
    Hanoi(num-1, by, from, to);
}

- Hanoi(3, 'A', 'B', 'C')를 호출 -> Hanoi(2)를 실행하고 모두 처리 -> console.log 처리 -> Hanoi(2) 실행 -> 끝나면 Hanoi(3) 끝  

=> Hanoi(2)는 내부적으로 Hanoi(1)을 호출 모두 끝나면 Hanoi(2) 종료 -> Hanoi(3)으로 돌아감

=> 콜스택에 쌓아놓음 : Hanoi(3), Hanoi(2) - 실행 후 이전의 함수로 돌아감

=> 이전의 연산에 덧붙여 연산을 할 때 재귀호출을 사용함