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

2020. 7. 11. 14:44· algorithm

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/

반응형

'algorithm' 카테고리의 다른 글

[recursion 응용] n queens problem  (0) 2020.07.22
[recursion 응용] Counting Cells in a Blob  (0) 2020.07.19
[recursion 응용] 미로찾기  (0) 2020.07.16
[recursion 예제3] 매개변수의 명시화  (0) 2020.07.15
[recursion 예제 2] 문자열, 2진수  (0) 2020.07.15
'algorithm' 카테고리의 다른 글
  • [recursion 응용] Counting Cells in a Blob
  • [recursion 응용] 미로찾기
  • [recursion 예제3] 매개변수의 명시화
  • [recursion 예제 2] 문자열, 2진수
이티권
이티권
programming, design
이티권
ET WORLD
이티권
전체
오늘
어제
  • 분류 전체보기 (85)
    • Web (43)
      • Three.js (1)
      • javascript (6)
      • React (2)
    • algorithm (18)
      • BOJ (6)
    • Record (9)
      • 생각 (6)
      • 경험 (3)
    • Art (7)
    • Technology (8)
      • Data (2)
      • Info (5)

블로그 메뉴

  • WEB
  • RECORD
  • ALGORITHM
  • TECH
  • ART

공지사항

인기 글

태그

  • 재귀함수
  • C언어
  • 포토샵
  • html tag
  • CSS
  • 불확신
  • ChatGPT
  • 기명함수 표현식
  • HTML
  • 깃 CLI
  • 맥북소리녹화
  • svgr
  • 레포지터리만들기
  • 알고리즘
  • 컴포넌트 통신
  • 시니어프론트엔드개발자
  • 뷰링크
  • 뷰라우터
  • 스프레드문법
  • 뷰 프롭스
  • 깃허브하는법
  • 페이지 링크
  • 순환
  • 컴퓨터공학힘든가요
  • js
  • 퓨 이벤트
  • vue.js
  • 나머지매개변수
  • 깃허브시작
  • 알고리즘문제

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
이티권
[recursion 예제 1] 피보나치, 최대공약수
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.