Recursion
์ฌ๊ทํธ์ถ / ์ํ์ด๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ ํจ์๊ฐ ์ํ๋์ค ์๊ธฐ ์์ ์ ๋ค์ ํธ์ถํ์ฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๊ธฐ๋ฒ์ด๋ค. ์ ์์์ฒด๊ฐ ์ํ์ ์ผ๋ก ๋์ด ์๋ ๊ฒฝ์ฐ์ ์ ํฉํ๋ค.
์๊ธฐ ์์ ์ ํธ์ถํ๋ ๊ฒ์ด๋ฏ๋ก ํ์ฌ ์์ ์ ์ฒ๋ฆฌํ๊ธฐ ์ํด์ ๊ฐ์ ์ ํ์ ํ์์์ ์ด ํ์ํ๋ค. ๋ฌธ์ ๋ฅผ ํ๋ฒ์ ํด๊ฒฐํ๊ธฐ๋ณด๋ค๋ ๊ฐ์ ์ ํ์ ํ์์์ ์ผ๋ก ๋ถํ ํ์ฌ ์์ ๋ฌธ์ ๋ถํฐ ํด๊ฒฐํ๋ ๋ฐฉ๋ฒ์ด๋ค. ์ํ ํจ์์์ ํ์ถํ ์ ์๋ basecase๊ฐ ๋ฐ๋์ ํ๋ ์ด์ ์์ด์ผํ๋ค.
์ํ ์๊ณ ๋ฆฌ์ฆ์์๋ ์ํ ํธ์ถ์ ํ๋ ๋ถ๋ถ(recursive case)๊ณผ ์ํ ํธ์ถ์ ๋ฉ์ถ๋ ๋ถ๋ถ(base case)์ด ์๋ค. ๋ง์ฝ ๋ฉ์ถ๋ ๋ถ๋ถ์ด ์๋ค๋ฉด ์์คํ ์ค๋ฅ๊ฐ ๋ฐ์ํ ๋๊น์ง ๋ฌดํํ ํธ์ถํ๊ฒ ๋๋ค.
๋ฉ์ถ๋ ๋ถ๋ถ์ด ๋ฐ๋์ ์์ด์ผํ๋ค. ์๋ค๋ฉด ์์คํ ์ค๋ฅ๊ฐ ๋ฐ์ํ ๋๊น์ง ๋ฌดํ ํธ์ถ
์ํ๊ณผ ๋ฐ๋ณต
์ํ
๋ฐ๋ณต
์ํ ํธ์ถ ์ด์ฉ(์ฌ๊ทํจ์)
for ๋๋ while
๊ตฌํ ์๋๊ฐ ๋น ๋ฆ
์ํ ์๋๊ฐ ๋น ๋ฆ
์ํ์ ์ธ ๋ฌธ์ ์์๋ ์์ฐ์ค๋ฌ์ด ๋ฐฉ๋ฒ์ด๋ ํจ์ ํธ์ถ์ ์ค๋ฒํค๋๊ฐ ์์ ์ ์๋ค.
์ํ์ ์ธ ๋ฌธ์ ์ ๋ํด์๋ ํ๋ก๊ทธ๋จ ์์ฑ์ด ์์ฃผ ์ด๋ ค์ธ ์๋ ์๋ค.
์คํ์๊ฐ : ์ปดํจํฐ๊ฐ ์คํํ๋ ์๊ฐ
๊ฐ๋ฐ์๊ฐ : ์ฝ๋ฉํ๋ ์๊ฐ
long int fact(int n){
if(n<=1) return 1; // basecase
else return(n*fact(n-1));
}
long int fact(int n){
int i, res = 1;
if(n<=1)return 1;
else{
for(i=n; i>=0;i--){
res = res * i;
}
return res;
}
}
๋ ๊ฐ์ง ๋ฐฉ๋ฒ ๋ค O(n)
์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค. ์ํ ํธ์ถ์ ์ดํดํ๊ธฐ ์ฝ๋ค๋ ์ฅ์ ์ด ์์ผ๋ ์ํ์๊ฐ๊ณผ ๋ฉ๋ชจ๋ฆฌ์ ์์ด์๋ ๋นํจ์จ์ ์ธ ๊ฒฝ์ฐ๊ฐ ๋ง๋ค.
๊ทธ๋ฌ๋ฏ๋ก ๊ฐ ๋ฌธ์ ์ ๊ฒฝ์ฐ์ ๋ง๊ฒ ๋ฐ๋ณต๊ณผ ์ํ์ ์ ํํด ํ์ด์ผํ๋ค. ( Dynamic Programming์์ ์ค์ )
์ค์ต

์ํ
#include <stdio.h>
int factorial(int n){
if(n<=1) return 1;
else return (factorial(n-1)*n);
}
๋ฐ๋ณต
#include <stdio.h>
int factorial(int n){
int res = 1;
if( n<=1 ) return res;
else{
for(int i = 2; i<=n;i++) res*=i;
return res;
}
}
๊ฑฐ๋ญ์ ๊ณฑ ๊ตฌํ๊ธฐ(x^n)
์ซ์ x์ n์ ๊ณฑ ๊ฐ์ ๊ตฌํ๋ ๋ฌธ์
์ํ
int power(int x, int n){
if(n==0)return 1;
else return (x*power(x,n-1));
}
์ด๋ ๊ฒ ํด๋ ๋๋ n์ด ์ง์์ธ ๊ฒฝ์ฐ์ ํ์์ธ ๊ฒฝ์ฐ๋ฅผ ๋๋ ์ ๊ตฌํ๋ฉด ์ฐ์ฐ๋์ด ๋ ์ค์ด๋ ๋ค.
int power(int x, int n){
if(n==0)return 1;
else if(n%2==0){
return power(x*x,n/2);
}else return x*power(x*x,(n-1)/2);
}
์์)
2^10
>> 10%2==0, power(4,5)
>> 5%2==1, 4*power(16,2)
>> 4%2==0, 4*power(256,1)
>> 1%2==1, 4*256(256*256,0) == 4*256*1
์ฌ๊ธฐ์ k๋ฒ์ ์ํ ํธ์ถ์ด ์ผ์ด๋๋ค. ํ๋ฒ ์ํํธ์ถ์ด ์ผ์ด๋ ๋๋ง๋ค 1๋ฒ์ ๊ณฑ์ ๊ณผ 1๋ฒ์ ๋๋์ ์ด ์ผ์ด๋๋ค. ์ ์ฒด ์ฐ์ฐ ์๋ k=log2(N)์ ๋น๋กํ๋ค. ์ฆ, ์๊ฐ๋ณต์ก๋๋ O(log2(n))์ด๋ค.
๋ฐ๋ณต
int power(int x, int n){
int res = 1;
if(n==0)return res;
else{
for(int i=1; i<=n;i++){
res*=x;
}
return res;
}
}
์ฌ๊ธฐ์ ์๊ฐ๋ณต์ก๋๋ O(n)์ด๋ค.
ํผ๋ณด๋์น ์์ด
ํผ๋ณด๋์น ์์ด์ ์ ์ ์์ฒด๋ ์ํ์ ์ด๋ ์ํ ํธ์ถ์ ์ฌ์ฉํ๋ฉด ๋นํจ์จ์ ์ธ ๋ํ์ ์ธ ์์์ด๋ค.
์ํ
int fib(int n){
if(n==0)return 0;
if(n==1)return 1;
return (fib(n-1)+fib(n-2));
}
fib(6)
>> fib(5) + fib(4)
>> fib(4)+fib(3) + fib(3)+fib(2)
>> fib(3)+fib(2) + fib(2)+fib(1) + fib(2)+fib(1) + fib(1)+fib(0)
์์ ๊ฐ์ด ๊ฐ์ ํญ์ด ๊ณ์ํด์ ์ค๋ณตํด์ ๊ณ์ฐ๋๋ฏ๋ก ๋นํจ์จ ์ ์ด๋ค.
๋ฐ๋ณต
int fib(int n){
if(n<2)return n;
else{
int i, current=1, last=0, tmp;
for(i=2;i<=n;i++){
tmp = current;
current += last;
last = tmp;
}
return current;
}
}
Tripple ํผ๋ณด๋์น ์์ด
1, 2, 3, 6, 11, 20, 37, 68 ...
์ํ
int fib_tri(int n){
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 2;
else{
return fib_tri(n-3)+fib_tri(n-2)+fib_tri(n-1);
}
}
ํ๋
ธ์ด ํ
๋ง๋ A์ ์๋ ์ํ์ ๋ง๋ C๋ก ์ฎ๊ธฐ๋ ๋ฌธ์ ์ด๋ค.
์กฐ๊ฑด
ํ ๋ฒ์ ํ๋์ ์ํ๋ง ์ด๋ํ ์ ์๋ค.
๋งจ ์์ ์๋ ์ํ๋ง ์ด๋ํ ์ ์๋ค.
ํฌ๊ธฐ๊ฐ ์์ ์ํ ์์ ํฐ ์ํ์ด ์์ผ ์ ์๋ค.
์ค๊ฐ์ ๋ง๋๋ฅผ ์์์ ์ผ๋ก ์ด์ฉํ ์ ์์ผ๋ ์์ ์กฐ๊ฑด๋ค์ ์ง์ผ์ผ ํ๋ค.
1๋จ๊ณ. ๋ง๋ A์์ ์๋ฐ(1~n-1)์ ๋ง๋ C๋ฅผ ์ด์ฉํด ๋ง๋ B๋ก ์ฎ๊ธด๋ค. Hanoi(m-1,a,c,b)
2๋จ๊ณ. ๋ง๋ A์์ ์๋ฐ(n)์ ๋ง๋ C๋ก ์ฎ๊ธด๋ค. if(m==1)
3๋จ๊ณ. ๋ง๋ B์์ ์๋ฐ(1~n-1)์ ๋ง๋ A๋ฅผ ์ด์ฉํด ๋ง๋ C๋ก ์ฎ๊ธด๋ค. Hanoi(m-1,b,a,c)
์ํ
void hanoi(int n, char a, char b, char c){
if(n==1)printf("์๋ฐ%d์ด ๋ง๋[%c]์์ ๋ง๋[%c]๋ก ์ฎ๊ฒจ์ง๋๋ค.",n,a,c);
else{
hanoi(n-1,a,c,b);
printf("์๋ฐ%d์ด ๋ง๋[%c]์์ ๋ง๋[%c]๋ก ์ฎ๊ฒจ์ง๋๋ค.",n,a,c);
hanoi(n-1,b,a,c);
}
}
Ackermann ํจ์
์ํค๋ฐฑ๊ณผ ์์ปค๋ง ํจ์์ ํจ์์ ๋ํ ์์ธํ ์ค๋ช ์ด ์๋ค.
์ํ
int ackermann(int m, int n){
if(m==0)return n+1;
if(m>0 && n==0)return ackermann(m-1,1);
return ackermann(m-1,ackermann(m,n-1));
}
๋ฐ๋ณต
basecase๊ฐ ์๋ค๋ฉด ์ํ์ด ์๋๋ค! ์ด๊ฒ์ ์ด์ ์ ๋๊ณ ์ฝ๋๋ฅผ ์ง๋ณด์๋ค.
int ackermann_loop(int m, int n){
int mm = m, nn = n;
while(mm!=0){
if(nn == 0) nn = 1;
else nn = ackermann_loop(mm,nn-1);
mm--;
printf("nn : %d \n",nn);
}
return nn+1;
}
2์ฐจ์ ๋ฐฐ์ด๋ก ๊ตฌํํ์ ๋๋ ๋ฒ์๋ฅผ ์ง์ ํด์ฃผ์ง ์์ผ๋ฉด ๊ณ์ํด์ ๋ฒ์๋ฅผ ์ด๊ณผํ๋ ๋ฌธ์ ๋ฐ์ํ๋ค.
int A[100][100];
int ackermann_loop(int m, int n){
for(int i = 0;i<=m;i++){
for(int j = 0; j<=50; j++){
if(i==0)A[i][j]=n+1;
else if(j==0)A[i][j]=A[i-1][j];
else{
int tmp = A[i][j-1];
A[i][j] = A[i-1][tmp];
}
}
}
return A[m][n];
}
๋ ๊ท์น์ ์ฐพ์์ ๊ตฌํํ๋ ๋ฐฉ๋ฒ๋ ์๋ค.
int Acker_nonrecursive3(int m, int n)
int i;
int val=2;
if(m==0) return n+1;
if(m==1) return n+2;
if(m==2) return 2*n+ 3;
if(m==3) {
// return pow(2, n+3) -3; ๋๋ ์๋ for loop ์ผ๋ก
for(i=1; i<n+3; i++)
val *=2;
return val -3;
}
if(m==4){
for(i=1; i< n+3; i++)
val *=val;
return val=val-3;
}
}
์์ ํ์
์์ ํ์์ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ฃผ์ ์์ด ๋ค ๊ณ์ฐํ๋ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์๋ฏธํ๋ค.
์ฌ๊ท ํธ์ถ์ ๊ฐ๋ฅํ ๋ฐฉ๋ฒ์ ์ ๋ถ ๋ง๋ค์ด ๋ณด๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์์ ํ์(Exhaustive Search)์ด๋ผ ๋ณผ ์ ์๋ค.
์ด๋ค ๋ฌธ์ ๋ฅผ ์์ ํ์์ผ๋ก ํด๊ฒฐํ๊ธฐ ์ํด์ ํ์ํ ๊ณผ์ ์ ๋๋ต ๋ค์๊ณผ ๊ฐ๋ค. 1. ์์ ํ์์ ์กด์ฌํ๋ ๋ชจ๋ ๋ต์ ํ๋์ฉ ๊ฒ์ฌํ๋ฏ๋ก, ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ๊ฐ๋ฅํ ๋ต์ ์์ ์ ํํ ๋น๋กํ๋ค. ์ต๋ ํฌ๊ธฐ์ ์ ๋ ฅ์ ๊ฐ์ ํ์ ๋ ๋ต์ ๊ฐ์๋ฅผ ๊ณ์ฐํ๊ณ , ์ด๋ค์ ๋ชจ๋ ์ ํ ์๊ฐ์์ ์์ฑํ ์ ์์์ง ๊ฐ๋ ํด๋ณด๊ณ ์ ์ฉํด์ผํ๋ค. 2. ๊ฐ๋ฅํ ๋ชจ๋ ๋ต์ ํ๋ณด๋ฅผ ๋ง๋๋ ๊ณผ์ ์ ์ฌ๋ฌ ๊ฐ์ ์ ํ์ผ๋ก ๋๋๋ค. ๊ฐ๊ฐ์ ์ ํ์ ๋ต์ ํ๋ณด๋ฅผ ๋ง๋๋ ๊ณผ์ ์ ํ ์กฐ๊ฐ์ด๋ค. 3. ๊ทธ์ค ํ ์กฐ๊ฐ์ ์ ํํด ๋ต์ ์ผ๋ถ๋ฅผ ๋ง๋ค๊ณ , ๋๋จธ์ง ๋ต์ ์ฌ๊ท ํธ์ถ์ ํตํด ์์ฑํ๋ค. 4. ์กฐ๊ฐ์ด ํ๋๋ฐ์ ๋จ์ง ์์ ๊ฒฝ์ฐ, ํน์ ํ๋๋ ๋จ์ง ์์ ๊ฒฝ์ฐ์๋ ๋ต์ ์์ฑํ์ผ๋ฏ๋ก basecase๋ก ์ ํํด ์ฒ๋ฆฌํ๋ค.
Last updated
Was this helpful?