[바킹독의 실전 알고리즘] 0x0B강 - 재귀

재귀(Recursion)

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

void func1(int n) {
	if(n == 0) return;
    cout << n << ' ';
    func1(n-1);
}

int func2(int n) {
	if(n == 0) return 0;
    return n+func2(n-1);
}

 

재귀로 푼다 == 귀납적인 방식으로 문제 해결

절차지향적 사고 vs. 귀납적 사고

void func1(int n){
	if (n==0) return;
    count << n << ' ';
    func1(n-1);
}

• 절차지향적 사고
  • ex. 1번 도미노가 쓰러진다 -> 2번 도미노가 쓰러진다 ...
    => 모든 도미노가 쓰러진다
  • 3 출력 -> func1(2) 호출 -> 2 출력 -> func1(1) 호출 -> 1 출력 -> func1(0) 호출
• 귀납적 사고
  • ex. 1번 도미노가 쓰러진다, k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다
    => 모든 도미노가 쓰러진다
  • func1(1)이 1을 출력,
    func1(k)가 k k-1 k-2 ... 1을 출력 -> func1(k+1) -> k+1 k k-1 ... 1을 출력

조건

• Base condition(= Base case)
  • 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함
• 모든 입력은 base condition으로 수렴해야 함

void func1(int n) {
	if (n==0) return;
    count << n << ' ';
    func1(n-1);
}

n = 0일 때 자기 자신 호출하지 않고 종료, 함수에 자연수만 넣으니 모든 입력은 결국에 n=0으로 수렴
IF. 둘 중 하나라도 지켜지지 않으면 런타임 에러 

정보

• 함수를 명확하게 정의
  • 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지
• 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수 만들 수 있음
• (+) 코드가 간결, (-) 메모리/시간 손해
• 자기 자신을 여러 번 호출 -> 비효율적일 수 있음
  • 이미 계산한 것을 또 계산함 => 다이나믹 프로그래밍 이용
  • ex. n번째 피보나치 수열을 반환하는 함수
    • n <= 1 -> 모든 입력에 대해 base condition에 수렴
    • 시간 복잡도: $O(1.618^n)$

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

• 자기 자신을 부를 때 스택 영역에 계속 누적 됨 (-> 런타임 에러 발생)

---

연습문제

거듭제곱

하노이 탑

Z

---