[2장] 순환

순환에 대한 문제풀이 내용이다.

순환(Recursion)이란? 알고리즘 내에서 자기 자신을 호출하는 것을 의미한다.

 

순환의 종류에는 직접 순환(Direct Recursion), 간접 순환(Indirect Recursion) 두 가지가 있다.

피보나치 수열, 팩토리얼 등은 함수 스스로를 호출하는 직접 순환이고,

간접 순환은 중간에 다른 함수를 거쳐서 돌아오는 것을 말한다.

 

이런 재귀 함수는 잘 사용하면 코드를 짧고 효율적으로 사용할 수 있겠지만, 

함수가 완전히 종료되기 전까지 스택의 메모리 구조에 쌓이기 때문에 반복문을 이용해 대체하기도 한다.

아래 문제들을 풀어보자. (순환 피보나치 수열 vs 반복 피보나치 수열 수행시간 비교)

 

06. 다음의 순환 호출 함수에서 잘못된 점은 무엇인가?

int recursive(int n)
{
if( n==1 ) return 0;
return n*recursive(n);
}

----> 종료에 해당하는 조건이 없다.

07. 다음의 순환 호출 함수에서 잘못된 점은 무엇인가?
int recursive(int n)
{
printf("recursive(%d)\n", n);
return n*recursive(n-1);
}

----> 재귀 함수에서 탈출 조건이 없다.

08. 다음 함수를 sum(5)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환 값
int sum(int n)
{
printf("%d\n", n);
if( n<1) return 1;
else return ( n +sum(n-1) );
}

---->  출력 :　5,　4,　3,　2,　1,　0
반환 : 16

09. 다음 함수를 recursive(5)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환 값
int recursive(int n)
{
printf("%d\n", n);
if( n<1) return 2;
else return ( 2*recursive(n-1)+1 );
}

---->  출력 :　5,　4,　3,　2,　1,　0
반환 : 5

10. 다음 함수를 recursive(10)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환 값
int recursive(int n)
{
printf("%d\n", n);
if( n<1) return -1;
else return ( recursive(n-3)+1 );
}

---->  출력 : 10, 7, 4, 1, -2
반환 : 3

11. 다음 함수를 recursive(5)로 호출하였을 때, 화면에 출력되는 내용
int recursive(int n)
{
if(n != 1) recursive(n-1);
printf("%d\n", n);
}

---->  출력 : 1, 2, 3, 4, 5

12. 다음 함수에서 asterisk(5)를 호출할 때 출력되는 *의 개수는?
void asterisk(int i)
{
if( i > 1) {
   asterisk(i/2);
   asterisk(i/2);
}
printf("*");
}

---->  7개

14. (1+2+3+....+n 계산하는 순환적인 프로그램)

#include <stdio.h>
int sum(int n)
{
 if(n == 1)
  return 1;
 
 return n + sum(n-1);   
}
void main()
{
 int n;
 
 printf("n을 입력하세요. : ");
 scanf("%d",&n);
 
 printf("1~n 까지의 합 : %d\n", sum(n));
}

15. (1+1/2+1/3+....+1/n 계산하는 순환적인 프로그램)

#include <stdio.h>
float div(float n)
{
 if (n == 1)
  return 1;
 
 return div(n-1) + (1/n);
}
void main()
{ 
 int n;
 printf("n을 입력하세요. : ");
 scanf("%d",&n);
 printf("%.2f\n", div(n)); 
}

 

17. (순환적인 프로그램을 반복적인 비순환 프로그램으로 바꾸기)

#include <stdio.h>
int i;
int sum(int n)
{
 int Sum = 0;
 for(i=1; i <= n; i++)
 {
  Sum += i;
 }
 return Sum;
}
void main()
{ 
 int n;
 printf("n을 입력하세요. ");
 scanf("%d",&n);
 printf("%d\n",sum(n));
}

 

20. 순환적인 피보나치 수열 프로그램과 반복적인 피보나치 수열 프로그램의 수행시간 비교

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int fib(int n)
{
 if(n==0)
  return 0;
 if(n==1)
  return 1;
 return (fib(n-1) + fib(n-2));
}
void main()
{
 int i,n;
 
 printf("n을 입력하세요. : ");
 scanf("%d",&n);
 
 clock_t start, finish;
 double duration;
 start = clock();
 
 for(i=1; i<=n; i++)
  printf("%d ",fib(i));
 printf("\n");
 
 finish = clock();
 duration = (double)(finish - start) / CLOCKS_PER_SEC;
 printf("running time -> %f\n", duration);
}

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int fib(int n)
{
 if(n < 2)
  return n;
 else
 {
  int i, tmp, current=1, last=0;
  for(i=2; i<=n; i++)
  {
   tmp = current;
   current += last;
   last = tmp;
  }
  return current;
 }
}
void main()
{
 int i,n;
 
 printf("n을 입력하세요. : ");
 scanf("%d",&n);
 
 clock_t start, finish;
 double duration;
 start = clock();
 
 for(i=1; i<=n; i++)
  printf("%d ",fib(i));
 printf("\n");
 
 finish = clock();
 duration = (double)(finish - start) / CLOCKS_PER_SEC;
 printf("running time -> %f\n", duration);
}

----> 같은 프로그램인데도 불구하고 순환 프로그램은 수행시간이 조금 더 걸렷다.
여기서 피보나치 수열을 구하는 프로그램은 순환보다 반복이 더 효율적이다.