[알고리즘] 1-1. 재귀 함수 기본

 

 재귀함수는 다시 반복되는 함수

 

-> 재귀함수를 쓰기 위해선 무한루프에 안빠지도록 설계

즉, 적어도 재귀함수에 빠지지 않는 한 가지의 경우의 수를 존재하도록

 

---

1. 기본 구조
2. 1~n까지의 합
3. n!
4. X^n
5. 피보나치 수열
6. 최대 공약수
7. 간단한 유클리드 함수

 

//1. 기본 구조
public static void func(int k){
 if (k<=0)
  return;
 else{
  System.out.println("Hello");
  func(k-1);
  }
 }
}

 

//2. 1~n까지의 합
public static int func(int n) {
 if (n==0)
  return 0;
 else
  return n + func(n-1);
  }
 }

 

//3. n! (팩토리얼)
public static int factorial(int n)
{
 if (n==0)
  return 1;
 else
  return n*factorial (n-1);
}

 

//4. X^n
public static double power (double x, int n) {
 if (n==0)
  return 1;
 else
  return x*power (x, n-1);
}

 

//5. 피보나치 수열
//f0 =0
//f1 =1
//fn = fn-1 + fn-2 (n>1인 경우)

public int fibonacci (int n) {
 if (n<2)
  return n;
 else
  return fibonacci (n-1) + fibonacci (n-2);
}

 

//6. 최대공약수 [유클리드 함수]
public static double 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);
}

// m>=n인 m,n은
// m이 n의 배수이면 n이며
// 그렇지 않으면, gcd (n, m%n)이다.

 

//7. 단순 유클리드 함수
// q=0일 때 	  : p
// 그렇지 않으면 : gcd(q, p%q)

public static int gcd(int p, int q) {
 if (q==0)
  return p;
 else
  return gcd(q, p%q);
}