728x90

순환(Recursion) 알고리즘 : 재귀함수

- 모든 순환함수는 반복문(Iteration)으로 변경가능, 모든 반복문은 recursion으로 표현가능 

- 순환함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 것을 가능하게 함, 하지만 오버해드가 있음(매개변수 전달, 엑티베이션 프레임 생성)

   (반복문에 비해 실행속도 불리, 경우에 따라 필요한경우도 있음)

-  순환함수가 되지 않기 위해 : 적어도 하나의 base case 존재,  Recursion을 반복하다보면 결국 base case로 수렴

- 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라


Factorial : n! 

0! = 1

n! = n x (n-1)! , n>0



Fibonacci Number

f0 = 0

f1=1

fn = fn-1 + fn-2   , n-1



Euclid Method : 최대공약수 

유클리드 방법 : 

m>=n 인 두 양수의 정수 m, n에 대해서 

m이 n 의 배수이면 gcd(m, n) =n 이고 그렇지 않으면  

gcd(m,n) = cde(n, m%n) 이다. 



Recursive Thinking : 순환적으로 사고하기

수학함수 뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다. 

문자열의 길이 계산

문자열 프린트

문자열 뒤집어 프린트

2진수로 변환하여 출력

배열데이터 정수들의 합


순환 알고리즘의 설계 DESIGNING RECURSION

- 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라

매개변수 암시화 : 순차탐색

// [0, n-1] 보통 생략... 즉 암시적인 매개변수  >>> 생략가능. 

매개변수의 명시화 : 순차탐색 

매개변수의 명시화 : 순차탐색 2

매개변수의 명시화 : 순차탐색 3

매개변수의 명시화 : 순차탐색 4

매개변수의 명시화 : 최대값 찾기

매개변수의 명시화 : 최대값 찾기 2

Binary Search : 이진검색








+ Recent posts