하향식 분석
1.recur(3) 실행
2.4 출력
3.recur(2) 실행
왼쪽 화살표 끝날 때까지 따라감 -> 바로 윗 상자의 가운데 부분을 출력-> 이어 오른쪽 화살표 따라감
꼭대기 부터 분석하면 같은 함수를 여러 번 호출해야해서 비효율적
상향식 분석
아래부터!!
n = 1일 때가 마지막이므로
recur(1) 실행하면
1.recur(0) 실행
2. 1 출력
3. recur(-1) 실행
recur(2) 실행하면
1.recur(1) 실행
2.2 출력
3.recur(0) 실행
recur(-1) : x
recur(0) : x
recur(1) : recur(0)|1|recur(-1) -> |1|
recur(2) : recur(1)|2|recur(0) -> 1|2|
recur(3) : recur(2)|3|recur(1) -> 1,2|3|1
recur(4) : recur(3)|4|recur(2) -> 1,2,3,1|4|1,2
재귀 알고리즘의 비재귀적 표현
꼬리재귀 recur(n - 2)의 의미
"n을 n-2로 바꾸고 함수의 시작지점부터 다시 돌린다."
-> n = n - 2로 반복문을 돌리면 된다.
하지만 recur(n - 1)은 제거 힘듬, n 값 출력 전까지 저장해야 해서
이때 스택(stack)을 이용해 완전히 재귀를 제거
순서
1. 스택에 4,3,2,1 쌓임
2. 다음 아래 조건문 실행되서 1을 pop하고 출력, 다음 n = n - 2로 업데이트 후 반복문 처음으로 돌아감
현재 1,2 출력
3. 2까지 똑같고 3을 pop할 때부터 다시 n = n - 2니까 다시 1이 push됨
현재 1,2,3 출력
4. 3번쨰에서 1을 push 했다가 다시 1부터 pop됨
현재 1,2,3,1 출력
5. 첫번째 조건문에서 n = -1이니까 4 pop됨
현재 1,2,3,1,4 출력
다음 1,2,3,1,4,1,2 출력
하노이의 탑
https://www.youtube.com/watch?v=aPYE0anPZqI
공부할 때 참고한 영상
큰 원반은 작은 원반 위에 쌓을 수 없다.
과정은 3단계로 나뉜다.
- 원반 1 ~ n - 1까지 1->2기둥으로 옮긴다.
- n 번쨰 원반을 3기둥으로 옮긴다.
- 원반 1 ~ n - 1까지 2->3기둥으로 옮긴다.
move 동작 원리를 직관적으로 설명하자면
일단 n개를 옮기는 동작을 실행 ex) 입력 값이 move(n,1,3)
그러려면 n - 1 개를 2번째로 옮겨야함 -> move(n - 1, 1, 2)로 다시 호출
거기서 n - 2 개를 3번째로 옮겨야함 -> move(n - 2,1,3)로 다시 호출
......
n = 1이면 그만 둠 , 1단계 끝
쭉 출력하다 마지막에 n번째 원반을 1->3기둥으로 보냄, 2단계 끝
위에 부분 재귀 돌고 그 아래 함수 실행됨 , 처음에 입력값(n,2,3) 으로 들어감
n - 1개를 1번쨰로 옮겨야함 -> move(n-1 , 2,1)로 다시 호출(위에꺼),반복
이러면 2기둥에 있는 1~ n -1 개 원반이 모두 3기둥으로 옮겨짐,3단계 끝
하지만 재귀는 메모리를 많이 잡아먹어서 남발하면 안된다.
다음은 비재귀적으로 푸는 방법이다.stack 자료구조를 사용한다.
(다음에 추가..)
