Search
Duplicate

순환 (Recursion) 의 개념과 기본 예제 1

태그
순환
Recursion
알고리즘
Recursion 이란?
간단하게 말하면 자기 자신을 호출하는 함수이다.
[예제 코드]
void func(...){ ... func(...); ... }
Java
복사
| 백준예제 순환을 찾아보자
순환의 개념(1) | 순환의 개념(2) | 순환의 개념(3)
조건을 잘 넣어주면 무한루프에 빠지지 않게 할 수 있다.
어떻게 해야 무한루프에 빠지지 않을까?
(1) Base case: 적어도 하나의 recursion 에 빠지지 않는 경우가 존재해야 한다.
(2) Recursive case: recursion 을 반복하다보면 결국 base case로 수렴해야 한다.
Factorial: n!
0!=10! = 1
n!=n(n−1)!n! = n(n-1)! (n>0)(n>0)
[ factorial 코드] | 깃허브 링크
public static int factorial(int n) { if (n==0) return 1; else return n*factorial(n-1); }
Java
복사
X 의 n 승
X0=1X^0 = 1
Xn=X∗Xn/XX^n = X*X^n/X if (n>0)(n>0)
[X 의 n 승 코드] | 깃허브 링크
public static double power(double x, int n) { if (n == 0) return 1; else return x*power(x, n-1); }
Java
복사
Fibonacci number
강의에서는 0 1 로 시작하였다.
[피보나치 수열 코드] | 깃허브 링크
public int fibonacci(int n) { if (n < 2) return n; else return fibonacci(n-1) + fibonacci(n-2); }
Java
복사
Euclid Method
m ≥ n 인 두 양의 정수 m 과 n 에 대해서 m 이 n 의 배수이면 gcd(m, n) = n 이고, 그렇지 않으면 gcd(m, n) = gcd(n, m%n) 이다.
[코드] | 깃허브 링크
public static int gcd(int m, int n) { if (m < n) { int tmp = m; m = n; n = tmp; // swap m and n } if (m % n == 0) return n; else return gcd(n, m%n); }
Java
복사
더 단순한 버전은 아래와 같다.
gcd(p, q) = p (if q=0) or gcd(q, p%q)
[코드] | 깃허브 링크
public static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p%q); }
Java
복사