Recursion Basics

배열의 정렬 여부 확인

bool isSorted(int arr[], int n) {
    if (n==1 || n==0) return true;
    if (arr[0] < arr[1] && isSorted(arr+1, n-1)) return true;
    return false;
}

배열의 시작위치와 크기를 1씩 감소시켜가며 맨 앞쪽을 계속 비교해나간다.

시간복잡도는 O(n)이지만 콜스택을 생각하면 n이 어느정도 커지면 실행이 안될것이다.

 

 

DP와 재귀는 Bottom-up, Top-down 여부에 차이가 있을 뿐 접근 방식은 거의 동일하다.