[AG] 재귀함수 깊이와 너비(DFS)

재귀함수 깊이와 너비

만약 재귀함수를 한번이 아니라 2번이 된다면 어떻게될까?

재귀 함수를 2번 호출을 해보자

 

그렇다면 구조는 이렇게 나오게된다.

그렇다면 이동 방향은?

 

왼쪽아래부터 내려가서 끝까지 내려갔음 다시 1로돌아와서 2로가고 다시 0까지 올라가고

오른쪽 1로가서 왼쪽2로가고 다시 1로올라와서 2로가고 끝까지 올라온다.

즉, 왼쪽 아래를 우선적으로 탐색한다.

 

출력결과

 

 

그럼 재귀2번호출은 알았으니 3번호출이 된다면?

 

 

구조는 이렇게 나오게 된다.

 

 

출력결과

즉 코드를 보면 알수있듯이

매개변수로 던지는 Level은 Depth(깊이)가 되고

재귀 호출의 횟수는 Width(너비)가 된다, 또는 Branch(나뭇가지)라고도 할수있다.

 

 

연습문제1

Level과 Branch를 입력 받고 그만큼 재귀호출을 해 주세요(출력결과 없음)

ex)

Level = 2Branch = 3

 

 

 

 

연습문제2

숫자 1개를 입력받고,

입력받은 Level 까지 재귀함수가 동작되도록 코딩해주세요

함수가 시작될 떄 Level을 출력하면 됩니다.

 

입력 : 2

출력 : 0122122

 

 

 

출력결과