[자료구조](2)[재귀]

재귀: 자기 자신을 호출하는 함수

• base case: 재귀 호출이 끝나는 조건
• recursive case: 자기 자신을 호출하는 부분
  base case 빠트리면 재귀가 안끝나니 주의!

재귀함수의 동작

-> 스택을 이용한다 (컴퓨터 구조 14 참고)
함수가 호출되면 스택을 할당받는다
자기 자신이 불릴 때마다 스택을 받는다
base case에 도달하면 LIFO로 나중에 불린 함수부터 스택을 반환한다.
예) 팩토리얼 계산 함수

int factorial(int n){
	if (n==0) return 1;
	else return (n * factorial(n-1));
}

base case = if (n==0) return 1;
recursive case = return (n * factorial(n-1));

실제로 프로그램을 돌려보면 각 단계를 거칠 때마다
스택 할당 -> base case -> 스택 반환(LIFO)

재귀 VS 반복

웬만한 재귀는 반복문으로 대체 가능하다

	재귀	반복
장점	직관적	재귀에 비해 빠름 메모리를 덜 차지
단점	오버헤드, 스택 관련으로 문제 발생 가능 느림	덜 직관적임

보통 재귀는 큰 문제가 작은 문제로 나누어질 때,
반복은 단순 반복일 때 사용한다.

 

재귀의 Big-O

피보나치 함수 fibo가

int fibo(int n){
	if (n<=1) return n;
	else return fibo(n-1) + fibo(n-2);
}

로 정의되어 있을 때,

피보나치 함수에서 fibo(4)를 계산한다면
fibo(4)
= fibo(3) + fibo(2)
= fibo(2) + fibo(1) + fibo(1) + fibo(0)
= fibo(1) + fibo(0) + fibo(1) + fibo(1) + fibo(0)
= 1+0+1+1+0 = 3
여기서 재귀할 때마다 2개씩 분기가 나뉜다.
따라서 O(2^n)이다...

계산 과정을 보면 중복된 값을 여러번 계산한다. 계산된 값은 저장해 알고리즘을 더 효율적이게 짠다면

int memo[100] = {0, 1};
int fibo2(int n){
    if (n<=1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibo2(n-1) + fibo2(n-2);
    return memo[n];
}

처럼 memo라는 배열에 계산한 값을 저장하고 만약 이미 계산되었다면 불러오기만 하는 함수가 된다.
이때의 시간 복잡도는 O(n)이다.

이처럼 재귀를 짤 땐 시간복잡도도 고려해야 한다.