Recursion

재귀 함수

재귀 함수란 자기 자신을 반복적으로 호출하는 함수를 칭한다

재귀 함수는 두개의 조건이 필요한데

• Base case : 자기 자신을 호출하지 않는 case, 반드시 하나의 경우가 필요하다 그렇지 않다면 무한 루프에 빠지게된다

• Recursive case : 자기 자신을 호출하는 case, 이 케이스가 반복적 실행을 수행하는데, 이 case를 계속 실행할 경우 base case로 수렴해야한다

재귀 함수의 예시

팩토리얼

function factorial (n){
    if(n===0) return n;

    return n * factorial(n-1);
}

x^n구하기

function pow (number, c){
    if(c===0) return 1;

    return number * pow(number, c-1);
}

유클리드 호제법

function gcd(n,m){
    if(n%m===0) return m;

    return gcd(m, n%m);
}

---

이때까지 호제법을 구현할 때는 n이 m보다 크거나 같아야하는 줄 알았는데

m이 n보다 클 경우에는 첫번째 재귀에서 n과 m의 위치가 바뀌기 때문에 swap해 줄 필요가 없다

피보나치 수열

function fibonacci(n){
    if(n<2) return n;

    return fibonacci(n-1) + fibonacci(n-2);
}

상술한 재귀 함수들은 모두 base case로 if문을 가지고 있고

각기 다른 방식으로 recursive case를 가지고 있다

재귀 함수 디자인

재귀 함수에는 매개변수가 명시적이어야한다

함수를 하나 살펴보자

function search(array, data){
    for(let i=0; i<=array.length-1;i++){
        if(array[i]===data) return i;
    }
    return -1;
}

주어진 배열과 데이터를 가지고 배열 안에 데이터가 있는지 찾는 함수이다

값이 있다면 인덱스를, 없다면 -1을 반환한다

이 함수에는 시작 지점이 명시되어있지 않다

으레 그렇게 생각하듯 배열의 시작점은 0이니까 암시적으로 0을 시작점으로 해서 검색을 시작하는데

이렇게 하면 재귀 호출을 할 수가 없다

function searchRecursion(array, start, data){
    if(start>array.length-1) return -1;
    if(array[start] === data) return start;
    return searchRecursion(array, start+1, data);
}

위의 함수를 재귀 함수로 바꿔봤다

달라진 점은 매개변수로 시작점을 명시해 줬다는 것

이렇게 시작 지점을 명시해서 매개변수로 넘기게되면 자기 자신을 호출할 때

매개 변수를 수정해서 검색할 구간을 지정하면서 반복시킬 수 있게된다