[recursion 예제 1] 피보나치, 최대공약수

resursion은 흔히 순환, 재귀로 불린다.

 

- 무한루프에 빠지지 않으려면?

       1. Base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재

        -> 실제로 무한루프에 빠진 코드는 범위를 안 정해서 그런 경우가 많았다

 

        2. Recursive case: recursion을 반복하다보면 결국 base case로 수렴해야 함

       ->recursion은 범위의 기준이 되는 곳으로 가서 코드가 마무리되기 때문

 

 

---

 

- recursion의 예제를 알아보자.

 

(1) 1~n까지의 합

#define _CRT_SECURE_NO_WANRNINGS
#include <stdio.h>
int main(void) {
	printf("%d",func(4));
}
int func(int n) {
	if (n == 0)
		return 0;
	else
		return n + func(n - 1);
}

결과: 10

1~n까지 합의 과정

순환함수와 수학적 귀납법의 관계

 

 

(2) Fibonacci number

#define _CRT_SECURE_NO_WANRNINGS
#include <stdio.h>
int main(void) {
	int i;
	for (i = 0; i <= 10; i++) {
		printf("%d  ", fibo(i));
	}
}
int fibo(int n){
	if (n < 2)
		return n;
	else
		return fibo(n - 1) + fibo(n - 2);
}

결과: 0  1  1  2  3  5  8  13  21  34  55

 

 

 

(3) 최대공약수 Euclid Method  ver.1

*m>=n인 정수 m,n에 대해서 m이 n의 배수이면 gcd(m,n)=n이고,

  그렇지 않으면 gcd(m,n)=gcd(n,m%n)이다.

#define _CRT_SECURE_NO_WANRNINGS
#include <stdio.h>
int main(void) {
	printf("%d", gcd(10, 4));
}
int gcd(int m, int n) {
	if (m < n) {
		int tmp = m; m = n; n = tmp; //swap m,n
	}
	if (m % n == 0)
		return n;
	else
		return gcd(n, m % n);
}

결과: 2

 

 

 

(4) 최대공약수 Euclid Method  ver.2

* gcd(p,q) = p (if q=0) or gcd(q, p%q) (otherwise)

#define _CRT_SECURE_NO_WANRNINGS
#include <stdio.h>
int main(void) {
	printf("%d", gcd(4, 10));
}
int gcd(int p, int q) {
	if (q == 0)
		return p;
	else
		return gcd(q, p % q);
}

 

 

 

---

프로그래밍 언어의 문법을 익히고 나서 실질적인 프로그래밍 실력을 기르기 위해 알고리즘 공부를 시작하기로 했다.

초반에 시간복잡도에 대한 내용부터 막히긴 했지만, 2강부터 차근차근 시작해보기로 한다. ;;

앞으로 포스팅은 아래의 강의를 참고해 업로드 할 예정이다!

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/