[자료구조] 2. 순환

2.1 순환의 소개

▶ Divide and conqure (분할정복) vs. Dynamic Programming(동적 프로그래밍)

• Divide and conqure: 큰 문제를 더 작은 하위 문제로 나누고, 각 하위문제를 독립적으로 해결한 다음, 그 결과를 합쳐서 전체 문제를 해결하는 방법 --> Recursive way (재귀적 방법)
• Dynamic programming: 하위 문제의 해결 결과를 저장하고, 나중에 동일한 하위 문제를 다시 해결하는 대신, 저장된 결과를 활용하여 중복 계산을 피하는 방법 --> Iterative way (반복적 방법)

 

▶ Activation Record

: 컴퓨터 프로그램에서 함수, 서브루틴 호출 시 생성되는 데이터 구조

--> 함수가 호출되었을 때 필요한 정보, 로컬 변수, 반환 주소 등을 저장하는데 사용한다.

 

팩토리얼 함수

▶ Recursive way vs. Iterative way

#1 Recursive way vs. Iterative way

 

 

2.2 거듭제곱값 계산: x^n

▶ Iterative way: O(n) vs. Recursive way: O(logn)

Iterative way vs. Recursive way

• Recursive way: 문제의 크기가 절반으로 줄어든다. --> O(logn)

 

 

2.3 피보나치 수열 계산

▶ Recursive way: O(2^n) vs. Iterative way

Recursive way vs. Iterative way

• Recursive way: 중간에 계산되었던 값을 기억하지 않고 다시 계산한다. --> O(2^n)

 

 

2.4 하노이탑 문제

 

 

Head recursion vs. Tail recursion

• Head recursion: return n*fact(n-1);
• Tail recursion: return fact(n-1)*n;

--> Head recursion: Iterative way로 바꿀 수 있다.

 

---

 

1. 처음에 asterisk_tail(4)가 호출됩니다. 함수는 i 값인 4를 받고, printf("*%d ", i)를 실행하여 "*4 "을 출력합니다.
2. 그런 다음, i가 1보다 큰지 확인합니다. i > 1은 참이므로 다음 단계로 이동합니다.
3. 재귀 호출이 두 번 일어납니다. asterisk_tail(4/2)와 asterisk_tail(4/2)가 각각 호출됩니다. 따라서 asterisk_tail(2)이 두 번 호출됩니다.
4. asterisk_tail(2)은 2를 받고, 먼저 printf("*%d ", 2)를 실행하여 "*2 "을 출력합니다.
5. 그 다음, i가 1보다 큰지 다시 확인합니다. i > 1은 참이므로 재귀 호출이 다시 일어납니다. asterisk_tail(2/2)와 asterisk_tail(2/2)가 각각 호출됩니다. 따라서 asterisk_tail(1)이 두 번 호출됩니다.
6. asterisk_tail(1)은 1을 받고, printf("*%d ", 1)을 실행하여 "*1 "을 출력합니다.
7. 이제 모든 재귀 호출이 완료되었으므로 각 호출의 실행 결과가 결합됩니다. 따라서 출력은 "*4 *2 *1 *1 *2 *1 *1"이 됩니다.

요약하면, 함수는 입력값 i를 출력한 다음, i가 1보다 큰 경우 재귀적으로 두 번 호출하여 출력을 생성하는 프로세스를 반복합니다.

 

1. 처음에 asterisk_head(4)가 호출됩니다. 함수는 i 값인 4를 받고, i > 1을 확인합니다. 조건이 참이므로 두 번의 재귀 호출이 발생합니다. asterisk_head(4/2)와 asterisk_head(4/2)가 호출됩니다. 따라서 asterisk_head(2)이 두 번 호출됩니다.
2. asterisk_head(2)은 2를 입력값 i로 받고, 먼저 i > 1을 확인합니다. 조건이 참이므로 두 번의 재귀 호출이 발생합니다. asterisk_head(2/2)와 asterisk_head(2/2)가 호출됩니다. 따라서 asterisk_head(1)이 두 번 호출됩니다.
3. asterisk_head(1)은 1을 입력값 i로 받고, printf("*%d ", 1)을 실행하여 "*1 "을 출력합니다.
4. 두 번째 asterisk_head(1) 호출이 완료되면 출력은 "*1 "입니다.
5. 첫 번째 asterisk_head(1) 호출이 완료되면 출력은 다시 "*1 "입니다.
6. 이제 asterisk_head(2)의 재귀 호출도 완료되었으므로 이 결과가 원래 호출에서 받아집니다.
7. asterisk_head(2)의 결과는 "*1 *1"이 되고, 이제 이 결과가 원래 asterisk_head(4) 호출로 돌아옵니다.
8. asterisk_head(4)의 결과는 "*1 *1 *2 *1 *1 *2 *4"가 됩니다.

즉, 함수는 printf 문을 마지막에 실행하며, 각 재귀 호출에서 결과를 받아서 출력 문자열을 생성합니다.

 

 

!!!

 

1. recursive(10)이 호출됩니다. n은 10이므로 "10 "이 화면에 출력되고, if 조건문을 통과하여 else 블록이 실행됩니다.
2. recursive(10-3) 즉, recursive(7)이 호출됩니다. n은 7이므로 "7 "이 화면에 출력되고, 다시 if 조건문을 통과하여 else 블록이 실행됩니다.
3. recursive(7-3) 즉, recursive(4)가 호출됩니다. n은 4이므로 "4 "가 화면에 출력되고, 다시 if 조건문을 통과하여 else 블록이 실행됩니다.
4. recursive(4-3) 즉, recursive(1)이 호출됩니다. n은 1이므로 "1 "이 화면에 출력되고, 다시 if 조건문을 통과하여 else 블록이 실행됩니다.
5. recursive(1-3) 즉, recursive(-2)가 호출됩니다. n은 -2이므로 " -2 "가 화면에 출력되고, if 조건문의 첫 부분 (n < 1)에 해당하여 -1이 반환됩니다.
6. 이제 recursive(-2)의 반환 값에 1을 더한 것이 recursive(1)의 반환 값이므로 -1 + 1은 0이 됩니다.
7. recursive(4)의 반환 값은 0 + 1이므로 1이 됩니다.
8. recursive(7)의 반환 값은 1 + 1이므로 2가 됩니다.
9. 마지막으로, recursive(10)의 반환 값은 2 + 1이므로 3이 됩니다.

따라서 recursive(10)을 호출할 때 출력되는 내용은 "10 7 4 1 -2"이고 반환값은 3입니다.