재귀

재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용한다. 

하나의 큰 문제를 해결하기 위해 다소 해결하기 쉬운 작은 문제의 결과를 조합한다.

 

재귀함수(Recursive Function)

함수 내부에서 자기 자신을 호출하는 함수로서

기저 부분(basis part)와 유도부분(inductive part)으로 이루어져 있다.

 

함수 호출은 프로그램의 메모리 구조 중 스택을 사용한다. 반복적으로 스택을 사용하기 때문에 

메모리 및 속도에서 성능 저하가 발생한다. 

 

함수 호출 시 기저 부분이 작동하지 않으면 자기 자신을 무한 호출하여 stackoveflow 발생

 

// n!에 대한 재귀함수

int fact(int n){
    if(n<=1) return 1;
    else{
    return n* fact(n-1);
        }
}

** 반복과의 비교

n이 커질수록 재귀가 반복보다 메모리와 연산속도 효율이 떨어진다.