재귀함수

재귀 함수

• 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미함
• 단순한 형태의 재귀 함수 예제
• '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력
• 어느정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력됨

function recursive(){

	console.log('재귀 함수를 호출합니다.');

	recursive();

}

recursive();

• 재귀 함수의 종료 조건
• 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 함.
• 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있음.

• 팩토리얼 구현 예제
• n! = 1 X 2 X 3 X ... X (n-1) X n
• 수학적으로 0!과 1!의 값은 1임.
• 내가 구현한 코드(자바스크립트)

function factorial(n){

    if(n <= 1)

        return 1;

    

    return n * factorial(n-1);

}

//수학적으로 0!과 1!은 1이다.

console.log(factorial(3));

/*

factorial(3)

= 3 * factorial(2)

= 3 * 2 * factorial(1)

= 3 * 2 * 1

*/

• 최대 공약수 계산(유클리드 호제법)예제
• 두개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로는 유클리드 호제법이 있음
• 유클리드 호제법
1. 두 자연수 A,B에 대하여(A>B) A를 B로 나눈 나머지를 R이라고 하고,
2. 이때 A와 B의 최대 공약수는 B와 R의 최대 공약수와 같음.
• 유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성할 수 있음. 

• 내가 구현한 코드(자바스크립트)

function getGCD(a,b){

    if(a % b == 0)

        return b;

     

     return getGCD(b, a%b);

}

console.log(getGCD(72,192)); // 24



/*

굳이 큰 수를 찾지 않아도, 작은수 큰수 순서로 입력하더라도 어차피 첫 단계에 뒤바뀌게 된다.

예를 들어 a=72, b=192라고 한다면

첫 단계에서 return getGCD(192, 72)로 바뀌게 되기 때문이다.

(72 % 192 = 72 이기 때문, 72를 192로 나누면 몫이 0, 나머지는 72)

*/

재귀함수 사용의 유의 사항

• 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있음.
• 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 함.
• 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음.
• 재귀 함수가 반복문보다 유리한 경우도 있고, 불리한 경우도 있음.
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임.
• 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀함수를 이용하는 경우가 많음.