part. 15 재귀 함수, 복잡도

Coldplay- Fix You

재귀 : 어떤 함수가 스스로를 호출하는 것

• 함수 내에서 자기 자신(함수)을 계속적으로 콜 하면서 풀어가는 방식
• 장점 : 알고리즘이 재귀로 표현하기에 자연스러울 경우 가독성이 좋음
• 단점 : 값이 리턴되기 전까지 호출마다 call stack을 새로 생성, 메모리를 많이 사용함

function factorial (n) {
  if(n < 0 ) return;
  if(n === 0) return 1;
  return n * factorial(x-1);
}
factorial(3);  // 3 * 2 * 1 // 3!
// 6

• 종료 조건 : 음수의 팩토리얼을 구하는것은 불가능. if (n < 0) return; 은 종료 조건. 음수 입력 값이 들어왔을 때, 팩토리얼 함수 작동 X.
• 기반 조건(Base case, 기저 상태) : 종료 조건과 비슷. 종료 조건은 모든 나쁜 데이터를 잡아내고 기반 조건은 재귀 함수의 목적이다. if (n === 0) return 1; n이 0까지 내려갔을 때, 팩토리얼을 구하는데 성공.
• 재귀 : 함수가 자기 자신을 호출. return n * factorial(n-1); 이 함수의 결과 값으로 곱해진 어떤 값을 반환한다.

function revStr(Str) {
  if (str === '') return '';
  return revStr(str.substr(1)) + str[0];
}
revStr('cat')
// tac

• 기반조건 : str === '' 문자열 내부에 아무런 글자가 없을때 목적 달성
• 재귀 : return rev(str.subStr(1)) + str[0];
• 종료조건 : 기반조건이 곧 종료조건, 문자열은 음수와 같은 특성이 없음.

• 피보나치 (Fibonacci)
  1+1 = 2
  2+3 = 5
  3+5 = 8
  5+8 = 13
  ...

function fibo(n) {
  if (n < 0) return -1;
  if (n < 2) return n;
  return fibo(n-2) + fibo(n-1);
}

원리 : fibo(3) 이었을때 구하는 과정을 보면, fibo(3-2) + fibo(3-1)
즉, fibo(1) + fibo(2).
fibo (4) 이었을때는 ? fibo(2) + fibo(3).

• fibo (2)를 예를들어서, else 문의 첫번째 메소드인 fibo(2-2)가 호출된다. n=0 이므로 if문에서 0리턴하고 종료.
  스택에 있던 fibo(2)로 다시 돌아가서, fibo(2-1)이 실행된다. n이 1이므로 1을 리턴하고 종료.
  // fibo(2-2) + fibo(2-1)
• fibo (3)을 예를들어서, else 문의 첫번째 메소드인 fibo(3-2)가 호출, n=1 리턴 종료.
  두번째 메소드인 fibo(3-1)이 수행, n=2 이므로 else를 타고 재귀가 다시 호출.

복잡도(Complexity Analaysis In The Real World)
Big-O Notation (시간 복잡도의 근사치 표시)

알고리즘: 시스템에 있는 문제를 해결하는 플랜
ex ) 2 ~ 16 사이의 숫자 중 제일 ‘차’가 큰 숫자 두개는 ?

첫번째 방법 ( 모든 숫자들을 하나 하나 비교 )
n * n = n^ , (n 제곱번의 복잡도 : n 제곱번의 operation ) ,
Big-O Notation : n^)

두번째 방법 ( 가장 작은 숫자와 가장 큰 숫자를 찾기 )
2 * n = 2n ( 2n 번의 operation ) , Big - O Notation : n )

세번째 방법 ( 이미 정렬 되어 있는 데이터를 이용 마지막 숫자와 첫번째 숫자를 - )
한번의 operation , Big - O Notation : 1 )