재귀 메모

1. 재귀 함수의 구조

 

재귀 함수의 경우 메인 함수의 스택 프레임 위에 push되어 쌓이는 구조를 가지고 있다.

 

이렇게 쌓이는 재귀함수는 각각이 자신이 돌아가야할 함수의 주소를 가지고 있으며,

 

알고리즘 문제를 풀 때 중요하게 생각할 점은 재귀함수 내의 함수 호출부 '이후'의 부분이 스택 구조로 실행된다는 점이다.

 

int recursive(){

(재귀함수 호출부 이전. 선형적으로 실행됨)

 

recursive();

 

(재귀함수 호출부 이후. 스택 구조로 실행됨)

}

 

 

2. 재귀함수와 DFS로 보는 활용

 

void D(int v) {
	if (v > 7) {
		return;
	}
	else {
		D(v * 2);//왼쪽 자식의 번호가 v*2
		D(v * 2 + 1);//오른쪽 자식의 번호가 v*2+1;
        cout << v <<endl;
	}
}

위와 같은 코드가 있을 때

D(v*2) 아래에 

D(v*2 + 1) 이 스택 구조로 쌓이고

 

또 D(v*2 + 1)의 각자 바로 위에 cout << v <<endl; 가 스택 구조로 쌓인다.

 

즉

 

D(8) - if문에서 탈출

D(4) -6

D(2) -6

D(1) -6line

 

과 같이 쌓였다가 D(4)의 아래가 스택처럼 쌓이고

 

D(9) - if문에서 탈출

D(4) -7

D(2) -6

D(1) -6

 

 

D(4) -8 == cout << 4 << endl;

D(2) -6

D(1) -6

 

D(5)

D(2) -7

D(1) -6

 

이렇게 쌓인 놈들을 pop할때마다 다시 stack이 쌓이게 되는 구조를 가지고 있다.

 

결국 시각화하면

트리의 DFS와 같은 형식이며, 각 함수는 왼쪽자식과 오른쪽 자식으로 이동할 때의 함수가 된다.

 

+추가

재귀함수를 여러번 사용하여 트리 구조의 DFS를 구현하는 경우,

위에서 썼던 예시 구조에서

 

int recursive(){

(재귀함수 호출부 이전. 선형적으로 실행됨. 바로 다음 나올 재귀함수부에만 적용되는 변동사항)

recursive();

(위의 변동사항을 초기화해주고)

 

(다른 노드로 가는 재귀함수 호출부 이전. 선형적으로 실행됨. 바로 다음 나올 재귀함수부에만 적용되는 변동사항) )

recursive();

}

 

선형적으로 실행되는 부분이 해당 노드로 이동하는 과정에서 사용되는 계산이 된다.

 

변동사항을 초기화해주는 부분의 코드를 쓰지 않고 독립적으로 동작하게 하고 싶다면,

변동 사항을 재귀함수의 인자 내에서 계산하도록 바꿔주면 된다,

 

예를들어 아래의 코드를

int recursive(int num){

	//바로 아래 노드에만 적용하고 싶은 수식
	num = num+1;
	recursive(num);

	//따라서 이 다음 취소
	num = num -1;
    
	recursive(num);

}

 

인자에서 계산되도록 하면

 

int recursive(int num){

	
	recursive(num+1);
	
    //다른 형제 노드에 영향 없음
	recursive(num);

}

 

위와 같은 구조로 사용하면 되는 것이다.

 

 

 

추가로 병합 정렬에서의 예시를 보면,

 자식 방문을 모두 끝낸 후 특정 행위를 하는, 후위 순회의 구조의 재귀는

 

void divide(int lt, int rt){

	int mid;
    if(lt < rt){
    	mid = (lt + rt)/2;
        
        //전위순회 식 위치
        divide (lt, mid);
        
        //중위순회. 왼쪽 자식 방문 후 수행할 식 위치
        
        divide(mid+1, rt);
        //후위 순회. 오른쪽 자식까지 모두 방문을 마치고 해당 노드가 수행할 식 위치
        //병합 정렬에서는 여기서 lt와 rt를 사용한 정렬을 진행한다
    }

}

 

위와 같은 방식으로 구현된다.

 

각자 자식마다 독립적으로 수행하고 싶은 '범위 설정'은 인자로 집어넣어서 독립적으로 수행되도록 코드를 짠 것.