[알고리즘/인프런정리] 1-1. Recursion 1

순환(recursion)? 자기 자신을 호출하는 함수이다.

 

main() {
  code();
}

code() {
  //...
  code();
}

-> 무한루프 빠진다.

 

main() {
  code2(4);
}

code2(int k) {
  if(k<=0) // Base case
    return;
  else {
    System.out.println("Hello");
    code(k-1); // Recursive case
  }
}

-> 4번 "Hello" 후 끝남.

code2(4); -> code2(3); -> code2(2); -> code2(1); -> code2(0); -> return;

 

 

recursion이 항상 무한루프에 빠지는 것은 아니다.

 

• 무한루프 빠지지 않을 조건

1. 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.

2. recursion 반복하다보면 결국 base case로 수렴해야 한다.

 

---

 

관련 기본 문제

 

(1) 1~n 합 -> O

 

(2) factorial: n! -> O

0! = 1

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

 

(3) x^n -> O

x^0=1

x^n = x*x^n-1, if n>0

 

(4) Fibonacci Number -> △ (피보나치 정의 기억하기!)

f0 = 0

f1 = 1

fn = f(n-1) + f(n-2), n>1

 

(5) Euclid Method(최대공약수) -> O (수학적으로 공식 이해는 안되지만 문제보고 풀기는 가능..)

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

아니면 gcd(m,n)=gcd(n,m%n)이다.

기본 버전, 단순 버전 확인

 

 

 

참고 강의

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

영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런