๐ Recursion ์ฌ๊ท
๐ซ ์ ์
ํ๋์ ํจ์์์ ์๊ธฐ ์์ ์ ๋ค์ ํธ์ถํด ์์ ์ ์ํํ๋ ์๊ณ ๋ฆฌ๋ฌ
์ด๋ค ๋ฌธ์ ๋ฅผ ์ฌ๊ท๋ก ํผ๋ค๋ ๊ฒ์ ๊ณง ๊ท๋ฉ์ ์ธ ๋ฐฉ์์ผ๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ฒ ๋ค๋ ๊ฒ
๊ท๋ฉ์ ์ธ ๋ฐฉ์ -> ์ผ๋ฐ์ ์ธ ์์๊ณผ๋ ์ฐจ์ด๊ฐ ์๋ค
์ผ๋ฐ์ ์ผ๋ก, ์์์ ๋ฐ๋ผ ํด์ผํ ์ผ์ด ์ ํด์ ธ์๋ ์ฝ๋
๊ท๋ฉ์ ์ผ๋ก
์ ์ผ ์์ ์๋ ๋๋ฏธ๋ ธ๋ฅผ ์ฐ๋ฌํธ๋ฆฌ๋ฉด ๋ชจ๋ ๋๋ฏธ๋ ธ๊ฐ ์ฐ๋ฌ์ง๊ฒ ์ฃ
์ ๋ชจ๋ ๋๋ฏธ๋
ธ๊ฐ ์ฐ๋ฌ์ง๋๊ฐ?
์์์๋ถํฐ 1๋ฒ 2๋ฒ ๋๋ฏธ๋
ธ๋ผ๊ณ ํ๋ค๋ฉด
- 1๋ฒ ๋๋ฏธ๋ ธ๊ฐ ์ฐ๋ฌ์ง๋ฉด 2๋ฒ ๋๋ฏธ๋ ธ๊ฐ ์ฐ๋ฌ์ง๊ณ , 2๋ฒ ๋๋ฏธ๋ ธ๊ฐ ์ฐ๋ฌ์ง๋ฉด 3๋ฒ ๋๋ฏธ๋ ธ๊ฐ ์ฐ๋ฌ์ง๊ณ , โฆ ์ด๋ฐ์์ผ๋ก ๊ณ์ ์งํ๋๊ธฐ ๋๋ฌธ์ ๋ชจ๋ ๋๋ฏธ๋ ธ๊ฐ ์ฐ๋ฌ์ง๋ค
- ์ํ์ ๊ท๋ฉ๋ฒ
- 1๋ฒ ๋๋ฏธ๋ ธ๊ฐ ์ฐ๋ฌ์ง๋ค
- k๋ฒ ๋๋ฏธ๋ ธ๊ฐ ์ฐ๋ฌ์ง๋ฉด k+1๋ฒ ๋๋ฏธ๋ ธ๋ ์ฐ๋ฌ์ง๋ค
2๋ฒ ๋ง์ ์๊ฐํ ํ์ ๋ฐ๋ก ๋ชจ๋ ๋๋ฏธ๋
ธ๊ฐ ์ฐ๋ฌ์ง๋ค๋ ๊ฒฐ๋ก ์ ๋๋ฌํ ์ ์์ด์ผ ํ๋ค
์ฆ, ์ฐ๋ฆฌ๊ฐ ์ง๊ธ๊น์ง ๋น์ฐํ๊ฒ ์๊ฐํ๋ ์ ์ฐจ์งํฅ์ ์ธ ์ฌ๊ณ ๋ฅผ ํํผํด์ผ ํ๋ค
1
2
3
4
5
6
void func1(int n)
{
if (n == 0) return;
cout << n << ' ';
func1(n - 1);
}
์ ์ฐจ์งํฅ์ ์ธ ์ฌ๊ณ ๋ก func1(3) ๊ฒฐ๊ณผ๊ฐ ์ 3 2 1์ธ์ง ์๊ฐํด๋ณธ๋ค๋ฉด
์ด ์ฝ๋๊ฐ ๋์ํ๋ ํ๋ฆ์ ๊ทธ๋๋ก ๋ฐ๋ผ๊ฐ๋ฉด ๋๋ค
func1(3)์ด ํธ์ถ๋๋ฉด 3์ ์ถ๋ ฅํ๊ณ func1(2)์ ํธ์ถ
func1(2)์ด ํธ์ถ๋๋ฉด 2์ ์ถ๋ ฅํ๊ณ func1(1)์ ํธ์ถ
func1(1)์ด ํธ์ถ๋๋ฉด 1์ ์ถ๋ ฅํ๊ณ func1(0)์ ํธ์ถ
func1(0)์ด ํธ์ถ๋๋ฉด ์ข
๋ฃ
์ด๋ ๊ฒ ๊ณผ์ ์ ๋ฐ๋ผ๊ฐ๊ณ ๋๋ฉด func1(3)์ ์คํํ์ ๋ 3 2 1์ด ์ถ๋ ฅ๋๋ค๋ ๊ฒ์ ์ ์ ์๋ค
๊ท๋ฉ์ ์ฌ๊ณ
func1 ํจ์๊ฐ n๋ถํฐ 1๊น์ง ์ฐจ๋ก๋ก ์ถ๋ ฅํ๋ ํจ์์์ ๊ท๋ฉ์ ์ธ ์ฌ๊ณ ๋ก ์ดํด
- func1(1)์ด 1์ ์ถ๋ ฅํ๋ค. ์๋ช ํ ์ฌ์ค
- _
- func1(k)๊ฐ k k-1 k-2 โฆ 1 ์ ์ถ๋ ฅํ๋ฉด, ์ฆ k๋ถํฐ 1๊น์ง ์ถ๋ ฅํ๋ฉด
- func1(k+1)์ k+1 k k-1 โฆ 1์ ์ถ๋ ฅํ๋ค. ์ฆ k+1๋ถํฐ 1๊น์ง ์ถ๋ ฅํ๋ค
์ด๊ฑธ ๋ณด์ด๋ ๊ฑด func1(k+1)์ด ํธ์ถ๋ ๋ ์ด๋ค ์ํฉ์ด ์๊ธฐ๋๊ฐ๋ฅผ ๋ณด๋ฉด ๋๋๋ฐ
k+1์ด ์ถ๋ ฅ๋ ์ดํ func1(k)๊ฐ ํธ์ถ๋๊ณ func1(k)๋ k๋ถํฐ 1๊น์ง ์ฐจ๋ก๋ก ์ถ๋ ฅํ๋ค ๊ฐ์ ์ ํ์ผ๋
func1(k+1)์ k+1๋ถํฐ 1๊น์ง ์ฐจ๋ก๋๋ก ์ถ๋ ฅํจ์ ์ ์ ์๊ฒ ์ฃ
์ด ๋ฌธ์ฅ์ด ์ฐธ์ด๋ฏ๋ก ๊ท๋ฉ์ ์ผ๋ก func1 ํจ์๊ฐ n๋ถํฐ 1๊น์ง ์ฐจ๋ก๋ก ์ถ๋ ฅํ๋ ํจ์์์ ์ ์ ์๊ฒ ๋ผ์
์ฌ๊ทํจ์์ ์กฐ๊ฑด
ํน์ ์
๋ ฅ์ ๋ํด์๋ ์๊ธฐ ์์ ์ ํธ์ถํ์ง ์๊ณ ์ข
๋ฃ๋์ด์ผ ํจ Base Condition/Base Case
๋ชจ๋ ์
๋ ฅ์ base Condition์ผ๋ก ์๋ ดํด์ผ ํจ
์ฌ๊ท์ ๋ํ ์ ๋ณด
- ํจ์์ ์ธ์๋ก ์ด๋ค ๊ฒ์ ๋ฐ๊ณ ์ด๋๊น์ง ๊ณ์ฐํ ํ ์๊ธฐ ์์ ์๊ฒ ๋๊ฒจ์ค์ง ๋ช ํํ๊ฒ ์ ํด์ผ ํจ
- ๋ชจ๋ ์ฌ๊ท ํจ์๋ ๋ฐ๋ณต๋ฌธ๋ง์ผ๋ก ๋์ผํ ๋์์ ํ๋ ํจ์๋ฅผ ๋ง๋ค ์ ์์
- ์ฌ๊ท๋ ๋ฐ๋ณต๋ฌธ์ผ๋ก ๊ตฌํํ์ ๋์ ๋นํด ์ฝ๋๊ฐ ๊ฐ๊ฒฐํ์ง๋ง ๋ฉ๋ชจ๋ฆฌ/์๊ฐ์์๋ ์ํด๋ฅผ ๋ด
- ํ ํจ์๊ฐ ์๊ธฐ ์์ ์ ์ฌ๋ฌ ๋ฒ ํธ์ถํ๊ฒ ๋๋ฉด ๋นํจ์จ์ ์ผ ์ ์์
- ๋๊ฐ์ ์ฐ์ฐ์, ์ด๋ฏธ ๊ณ์ฐํ ๊ฐ์ ์ฌ๋ฌ ๋ฒ ๋ค์ ํ๊ฒ ๋๋
- ํผ๋ณด๋์น, n๋ฒ์ ๋ง์ ์ ํ ๊ฒ ๊ฐ์ง๋ง, ์๊ฐ๋ณต์ก๋๋ O(1.618n), n์ ๋ํ ์ง์ํจ์ ๊ผด
- ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ ํตํด O(n)์ ํด๊ฒฐํ ์ ์๋ค
- ์ฌ๊ทํจ์๊ฐ ์๊ธฐ ์์ ์ ๋ถ๋ฅผ ๋ ๋ฉ๋ชจ๋ฆฌ ์์ญ์์ ์คํ ์์ญ์ ๊ณ์ ๋์ ์ด ๋จ
- ๋ฌธ์ ์์์ ๋ฉ๋ชจ๋ฆฌ ์ ํ์ด ์๋๋ฐ, ์ผ๋ถ ์ปดํ์ผ ํ๊ฒฝ์์๋ ์คํ ์์ญ์ ๋ฉ๋ชจ๋ฆฌ๊ฐ ๋ณ๋๋ก ์๊ฒ ์ ํ๋์ด ์๊ธฐ๋ ํ๋ค
- ์ฌ๊ท๋ก ํ์์ ๋ ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๊ฐ ๋๋ฉด, ์ด์ฉ ์ ์์ด ๋ฐ๋ชฉ๋ฌธ์ผ๋ก ๋ฌธ์ ๋ฅผ ํ์ด์ผ ํ๋ค
- ์ฐธ๊ณ : ์คํ ๋ฉ๋ชจ๋ฆฌ์๋ ์ง์ญ ๋ณ์๋ ๋ค์ด๊ฐ๋ค
- ๊ฑฐ๋ญ์ ๊ณฑ
- ๋ชจ๋๋ฌ ์ฐ์ฐ ab mod m
- ๊ณฑํ๋ ์ค๊ฐ์ค๊ฐ ๊ณ์ m์ผ๋ก ๋๋ ์ ๋๋จธ์ง๋ง ์ฑ๊ฒจ๊ฐ๋ฉด ๋๋ค
231241234 * 12412 * 234
์ ์ผ์ ์๋ฆฌ๋ฅผ ๊ตฌํ ๋ ์ฆ 10์ผ๋ก ๋๋ ๋๋จธ์ง๋ ์ผ์ ์๋ฆฌ4 * 2 * 4
๋ง ๊ณฑํด์ ๊ตฌํ๋ฉด ๋๋ค๋ ๊ฒ์ ์๊ณ ์๋ค- ๋ชจ๋๋ฌ ์ฐ์ฐ์์๋ 10์ด ๊ทธ๋ฅ m์ผ๋ก ๋ฐ๋ ๊ฒ
- ab mod d๋ฅผ O(b)์ ๊ตฌํ ์ ์๋ค
- ๊ณฑ์
- b๊ฐ 21์ต?
- ํํธ1 an * an = a2n
- ํํธ2 1258 โก 4(mod 67) -> 12116 โก 16(mod 67)
- ์ ๊ท๋ฉ๋ฒ์ผ๋ก ํด๊ฒฐํ ์ ์๊ฒ ๋ค
- 1๋ฒ ๋๋ฏธ๋ ธ๊ฐ ์ฐ๋ฌ์ง๋ค
- k๋ฒ ๋๋ฏธ๋ ธ๊ฐ ์ฐ๋ฌ์ง๋ฉด k+1๋ฒ ๋๋ฏธ๋ ธ๋ ์ฐ๋ฌ์ง๋ค
- _
- 1์น์ ๊ณ์ฐํ ์ ์๋ค
- k์น์ ๊ณ์ฐํ์ผ๋ฉด 2k์น๊ณผ 2k+1์น๋ O(1)์ ๊ณ์ฐํ ์ ์๋ค.
- -> 2k์น๊ณผ 2k+1์น ๋ชจ๋ k์น์ ๊ณ์ฐํ์ผ๋ฉด O(1)์ ๊ณ์ฐํ ์ ์๋ค
- ๋ ๋ฌธ์ฅ์ด ์ฐธ์ด๊ธฐ ๋๋ฌธ์ a์ ์์์ ์ง์์น์ ๊ท๋ฉ์ ์ผ๋ก ๊ณ์ฐํ ์ ์๋ค
- b๊ฐ ์ ๋ฐ์ฉ ๊น์ด๊ธฐ ๋๋ฌธ์ O(log b)
- ํ๋
ธ์ด ํ ์ด๋ ์์
- n-1๊ฐ์ ์ํ์ ๊ธฐ๋ฅ1์์ ๊ธฐ๋ฅ2๋ก ์ฎ๊ธด๋ค
- n๋ฒ ์ํ์ ๊ธฐ๋ฅ 1์์ ๊ธฐ๋ฅ 3์ผ๋ก ์ฎ๊ธด๋ค
- n-1๊ฐ์ ์ํ์ ๊ธฐ๋ฅ 2์์ ๊ธฐ๋ฅ3์ผ๋ก ์ฎ๊ธด๋ค
- -> ์ํ์ด n-1๊ฐ์ผ๋ ์ฎ๊ธธ ์ ์์ผ๋ฉด ์ํ์ด n๊ฐ์ผ ๋์๋ ์ฎ๊ธธ ์ ์๋ค
- ์ํ์ด 1๊ฐ์ผ๋ ์ํ์ ๋ด๊ฐ ์ํ๋ ๊ณณ์ผ๋ก ์ฎ๊ธธ ์ ์๋ค
- ์ํ์ด k๊ฐ์ผ๋ ์ฎ๊ธธ ์ ์์ผ๋ฉด ์ํ์ด k+1๊ฐ์ผ๋์๋ ์ฎ๊ธธ ์ ์๋ค
- ํจ์์ ์ ์
- base condition
- ์ฌ๊ท์
๐ซง
์ฌ๊ท
๋ฐ๋ณต๋ฌธ๊ณผ ๊ฐ์ ์ผ์ ํ ์ ์๊ณ , ๋ฐ๋ณต๋ฌธ๋ณด๋ค ์ข ๋๋ฆฌ๊ณ (ํจ์ ํธ์ถ), ๋ ํฌ์ง๋ง(ํธ์ถ์คํ ๋ฉ๋ชจ๋ฆฌ), ๋ ๋ช
ํํจ
์ฑ๋ฅ์ ์ํด์๋ผ๋ฉด ๋ฐ๋ณต๋ฌธ, ๋ฅ๋ฅ ์ ์ํด์๋ผ๋ฉด ์ฌ๊ท๋ฅผ
์ ์ฌ์ ์์ ๋ง๊ฒ
๊ธฐ๋ณธ๋จ๊ณ base case : ์ฌ๊ท ํจ์๊ฐ ์๊ธฐ ์์ ์ ๋ค์ ํธ์ถํ์ง ์๋ ๊ฒฝ์ฐ
์ฌ๊ท๋จ๊ณ recursive case : ์ฌ๊ท ํจ์๊ฐ ์๊ธฐ ์์ ์ ํธ์ถ
@ ํธ์ถ ์คํ
@ ๊ผฌ๋ฆฌ ์ฌ๊ท Tail Recursion