순환-(개념 설명)

채재헌·2022년 4월 5일
0

📌<순환>

:순환이란 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를
해결하는 기법

📝펙토리얼 프로그래밍#1

int factorial(int n)
{
	if (n == 0)
		return(1);
	else
		return(n*factorial(n - 1));

}

==>🎈구조 원리
//int value = 1 1;//1factorial(0)//<-factorial(1);
//int value2 = 2 1 1//factorial(2);
//int value3 = 3 2 1 1//factorial(3)
//int value2= 4
321*1//factorial(4)

=> 코드 해석 : ,예제 펙토리얼 프로그래밍 #1을 해석하자면 factorical()함수에 n의 값을 넣어 만약 n이 0이라면 리턴 1을하여 팩토리얼 함수에서 빠져나오고 아니며 리턴
(n*factorial(n-1))의 값을 리턴하여 위에 나와있는
🎈#1의 구조 원리를 통해 함수안에서 돌아가는것을 살펴 볼수 있다.

# 📝 펙토리얼_iter 
int factorial_iter(int n)
{
	int k, v = 1;
	for (k = n; k > 0; k--)
		v =v* k;
		//v*=k;
	return(v);
}

위에 같은 코드를 재귀함수 말고 펙토리얼 for()문을 이용하여
코드의 복잡성을 줄일 수 있다.

📌 <순환 알고리즘의 구조>

만약 순환 호출을 멈추는 부분이 없다면
=>시스템 오류가 발생할때까지 무한정 호출하게 된다.(stackoverflow)

✨# 스택 오버플로우(StackOverflow)란??

스택 오버 플로우를 들으면 우리가 먼저 드는 생각은 개발 커뮤니티인 스택오버플로우 이다. 하지만 여기서 이야기하는 스택 오버 플로우는 지정한 스택 메모리 사이즈보다 더 많은 스택 메모리를 사용하게 되어 에러가 발생하는 상황을 일컫는다.

스택 오버 플로우에 대한 자세한 이야기는 다른 곳에서 하겠다.

📌 <팩토리얼의 반복적 구현>

#반복적인 함수 slow power

power(x, n)
if n == 0
then return 1;
else if n이 짝수
then return power(x제곱, n / 2);
else if n이 홀수
then return x * power(x제곱, (n - 1) / 2);

#//순환적인 함수 power
double power(double 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);
}

위에 나와있는 #순환적인 함수 power와 #반복적인 함수인 slow power 코드를 비교해보면 #순환적인 함수 power 코드의 시간복잡성은 O(logn)이고
후자인 #반복적인 함수 slow power은 O(n) 인것을 알 수 있다.
그리고 실행 속도 또한 전자가 0.47초 후자가 7.17초를 확인함으로써
전자 순환적인 함수 power 코드가 후자인 반복적인 함수 slow power 보다 실행 속도가 빠르고 시간 복잡성이 덜해 알고리즘의 효율성이 높다.

🎈<피보나치 수열의 계산>#1

int fib(int n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	return (fib(n - 1) + fib(n - 2));
}

<피보나치 수열의 반복 구현>
int fib_iter(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;

int pp = 0;
int p = 1;
int result = 0;

for (int i = 2; i <= n; i++) {
	result = p + pp;
	pp = p;
	p = result;
}
return result;

}

느낌점 : 이번 수업을 통해서 자료구조에서 값을 검색 할때 사용되는 순환에 대해서 공부를 했다. 순환이란 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법으로 재귀함수를 활용한 사례이다. 이에 대한 예제로 ,예제 펙토리얼 프로그래밍 #1을 해석하자면 factorical()함수에 n의 값을 넣어 만약 n이 0이라면 리턴 1을하여 팩토리얼 함수에서 빠져나오고 아니며 리턴
(n*factorial(n-1))의 값을 리턴하여 위에 나와있는
🎈#1의 구조 원리를 통해 함수안에서 돌아가는것을 살펴 볼수 있었다.나는 이번 수업을 통해 재귀함수를 이용한
순환 호출법을 배웠고 재귀함수의 원리를 더 이하여 다양한 재귀함수 예제를 백준에서 풀어야겠다는 생각이 들었다.

0개의 댓글