재귀와 역추적

 

재귀(recursion)
역추적(backtracking)

재귀(recursion)?
자기 자신을 반복해서 호출 하는 모든 함수를 재귀적이라 함 
재귀적 방법은 보다 작은 문제로 작업 하기 위해 자기 자신의 복사본을 호출함으로 문제를 해결 
이것을 '재귀 단계' 라고 한다.

보통 루프절은 컴파일 되거나 해석될때 재귀 함수로 바뀜 
정렬, 검색, 탐색문제에 흔희 간단한 재귀 방식을 가지고 해결 

재귀 함수는 하위 작업을 수행하기 위해 자신을 호출하여 부분적으로 작업을 수행 
어느 순간 함수는 더이상 자신을 호출하지 않고도 수행 할수 있는 하위 작업에 이르게 됨 
함수가 더이상 재귀 호출 되지 않는 이경우를 가리켜 'base case'(종료 조건)라 함 
하위 작업 수행을 위해 자기 자신을 호출하는 경우를 'recursive case' (재귀 조건)라 함 

 

 

if(test for the base case)
    return some base case value
else if(test for another base case)
    return some other base case value
//재귀조건 (the recursive case)
else 
   return (some work) and then (재귀호출)
 

 

재귀와 메모리 (Visualization)
각 재귀호출은 메모리에 해당 함수의 새로운 복사본을 만듬 
함수가 종료(즉, 어떤 데이트를 반환) 되면 반환 함수의 복사본은 메모리에서 제거됨 
재귀적 해법은 간단해보이지만 시각화하고 추적하는데 시간이 걸림 

 

1부터 n까지를 역으로 출력 

class Solution3{
        public Solution3(){
            this.Print(10);
        }
 
        int Print(int n){
            Console.WriteLine(n);
            //base case
            if(n == 1){
                return 1;
            }else{
                //recursive case 
                return Print(n-1);
            }
        }
    }

 

재귀 vs 반복 

재귀 
- 종료 조건에 도달하면 종료 
- 각 재귀호출은 스택 프레임상의 추가 공간을 필요 
- 무한 재귀에 봉착하면 프로그램은 메모리 부족으로 스택오버플로우가 발생 

반복 
- 조건이 false일때 종료 
- 각 반복 구문은 추가적인 공간을 필요로 하지 않음 
- 끝나지 않은 무한 루프는 추가적인 메모리가 생성되지 않기 때문일수 있음 
- 문제를 반복적인 방법으로 해결하는것이 항상 재귀적인 해결방법보다 명확한것은 아님 

 

 

재귀 방식에 대한 참고 사항 

- 재귀적 알고리즘은 재귀조건과 기저조건이 있음 
- 모든 재귀함수는 기저조건에서 종료 되어야 함 
- 일반적으로 반복 방식의 해결책은 재귀방식보다 효율적 (함수호출 오버헤드에 기인)
- 재귀 알고리즘은 스택을 사용하는 재귀 함수 호출없이 구현할수 있지만 일반적으로 득보다 실이 큼 (재귀로 풀수 있는 모든 문제는 반복적으로 풀수 있다는 말)
- 몇몇 문제에서 명확한 반복 알고리즘이 존재 하지 않을수 있음
- 몇몇 문제에서 다른 방법들에 비해 재귀적인 해결책이 적합 할수 있음 

재귀 알고리즘의 예 
- 피보나치 수열, 팩토리얼 찾기
- 병합 정렬, 퀵 정렬
- 2진 검색 
- 트리탐색과 많은 트리 문제 : 중위(InOrder), 전위(PreOrder) , 후위 (PostOrder)
- 그래프 탐색 : 깊이 우선 (DFS [Depth First Search]) , 너비 우선 (BFS[Breath First Search])
- 동적 프로그래밍(DP) 예제 
- 분할과 정복 알고리즘 
- 하노이의 탑
- 역추적 알고리즘