재귀(recursion)

재귀 호출(recursive call)이란?

재귀 호출이라 함은 함수를 호출 할 때 자기 함수를 자기가 호출 호출을 말함.
void recursion()
{
   recursion(); // 재귀 호출 
}

int main()
{
   recursion();
}
물론 위 프로그램은 무한 루핑에 빠지는 재귀이다.
void recursion(int n)
{
   printf("%d\n",n);
   recursion(n+1); // 재귀 호출 
}

int main()
{
   recursion(1);
}
프로그램 언어에서 재귀 호출이 가능한 이유는 함수가 불리워 질때 마다 c 언어에서는 auto 변수, pascal 언어에서는 지역변수는 새로운 공간(스택)에 자리를 확보하기 때문이고 ,
재귀 호출에서 무한 반복이 빠지지 않기 위해서는 반드시 끝나는 종료 조건이 존재해야 한다. 이를 base 혹은 terminal 조건 이라 한다
(보기) 다음 프로그램을 실행하면 결과는?
void print(int n){
   if (n != 1)  print (n-1);
   printf("%d\n",n);
}

int main()
{
   print(3);
}
(풀이) 함수내의 if 문의 형식은
if ( 조건식 ) A
B
조건식이 참이면 A 실행후 , B 를 실행한다.
조건식이 거짓이면 B 를 실행한다.
n 이 3 과 2 인 경우,
if 의 조건식이 참이므로 두 문장이 수행된다.
print(n-1);
printf("%d\n",n);
print() 함수의 수행이 종료되어야 printf() 함수가 실행될 것이다.
n 이 1 인 경우
if 의 조건식이 거짓이므로 아래 한 문장이 수행된다.
printf("%d\n",n);
그림으로 나타내면 ,

(유제) 위 보기를 참고하여 10 진수를 받아 , 해당 2 진수로 변환하는 프로그램을 작성하라.
(보기2) 다음 프로그램의 실행결과는?
int fibo(int n){
   if (n==0) return 0;
      else if (n==1) return 1;
         else return return fibo(n-1)+fibo(n-2);
}

main(){
   printf("%d",fibo(4));
}
위 재귀호출에서 주목해야 할 것은 제어의 흐름이다. fibo(4) 가 호출된 경우
fibo(3) + fibo(2)
이 호출되는데 , 수행 순서는 fibo(3) 의 수행을 끝내고 fibo(2) 의 수행을 시작한다는 데 있다.
위의 재귀호출에서 알아야 할 사항은 제어의 흐름을 알아야 한다. 아래 그림의 반원위의 숫자는 이 재귀호출이 호출되고 리턴되는 순서이다.

이 보기는 유명한 피보나치 수열이다.

f(0)=0
f(1)=1
f(n)=f(n-1) + f(n-2)
0 , 1 , 1 , 2 , 3 , 5 , 8 , 13,
int fibo(int a,int b , int n){

   if (n<=1) return b;
     else return fibo(b,a+b,n-1);
}

main(){
   printf("%d\n",fibo(0,1,8));
}
(유제1) n! 구하는 프로그램
(hint)

f(n) = n * f(n-1)
f(0) = 1

n= ] , n!=[]

(유제 2) x 의 y 승을 구하는 재귀 프로그램(x^y)

(hint)

3⁵=3 * 3⁴
3⁰=1

(유제 3) gcd 구하는 프로그램

(hint) 12,8 의최대 공약수를 구하는 뉴클리드 알고리즘

즉 n 값을 m 으로 , m%n(m 을 n 으로 나눈 나머지) 값을 n 값으로 두는 과정을 반복하면서 n 값이 0 이 될때의 m 값이 두 수의 최대 공약수가 됨.

gcd(m,n) 는 gcd(n,m%n)
n 이 0 일 때 m 이 최대 공약수

[질/답]

[홈으로] [뒤 로]

[푼 후(0)]