[2] 재귀함수 공부

함수

지역변수 : 함수 안에서 선언한 변수

전역변수 : 어디에서나 같은 변수 (공통 사용)

+ 함수의 파라미터(변수가 가지고 있는 값을 준 것)도 지역변수로 취급.

 

재귀함수

함수가 자기 자신을 호출하여 문제를 해결하는 방법

DFS, Union Find, 분할정복, DP(Top-Down)에서 활용.

void func1(){
	func1();
}

int main(){
	func1();
	return 0;
}

이때, 너무 많이 쌓이면서 Stack Overflow(메모리 부족) 발생.

특정 함수에서 멈추라고 해줘야 함.

작동을 멈출 함수를 정해야하고, 반복되는 함수들이 같은 함수이더라도 구분할 수 있어야 함. 

⇒ 변수 활용 (매개변수 or 전역변수 활용 가능 / 매개변수 주로 사용) → void func1(int a)

 

재귀함수를 기준으로

앞) 함수들을 진행하면서 처리할 것

뒤) 함수들을 되돌아 오면서 처리할 것 (다음 함수의 작업이 모두 끝난 후)

 

기저조건 : 반복을 끝낼 조건

#include<iostream>
using namespace std;

void func1(int a) {
    // ----- 2. 끝낼 조건(기저조건)
    if (a > 64)
    {
        // ------ 끝내면서 처리
        cout << "\n";
        return; // <- 바로 끝내라
    }

    // ------ 3-1) 'box'들을 진행해 나가면서 처리
    // 다음 box로 가기 '전'
    cout << a << " "; // <- 가면서 진행


    // ------ 1. 현재 박스에서 다음 박스로 진행(재귀의 기본 구조)
    // 다음 box에서는 내가 갖고있던 a보다 1개 더 큰 값으로 사용해라
    // '다음 box'로 가라!
    func1(a * 2);



    // ------ 3-2) 'box'들을 되돌아 오면서 처리(다음 box가 할게 전부 끝나고)
    // 다음 box를 갔다온 '후'
    cout << a << " "; // <- 돌아오면서 진행
}


void func2(int a) {
    // 2. 기저조건(3보다 커지면 잘못된 박스)
    if (a > 3) return;

    // 3. 하고 싶은 처리
    cout << a;

    // 1. 재귀 기본 구조
    func2(a + 1); // 일단 내 박스는 스탑하고 다음 박스로 가라

    func2(a + 1);

}

int main() {
    //func1(1);
    func2(0);
    return 0;
}

- 특징

1. 함수가 자기 자신을 호출함.

2. 무조건 종료가 필요함. (기저 조건 작성 필수)

3. 이론상으로는 재귀를 반복문으로 구성할 수 있지만 실제로는 어려움.

 

- 작성법

1. 기저 조건 : 언제 종료해서 빠져나올지 → if() return;

2. 수행 내용 : 어떤 작업을 반복할지 → cout << ?? ;

3. 재귀 구성 : 어떻게 다음 재귀를 진행할지 → func(now + 1);

 

- 재귀 활용

모든 조합 / 순열을 찾을 수 있다! 즉, 모든 경우의 수를 확인 가능.

1) path : 경우의 수를 기록하는 DATA

2) Backtracking : 경우의 수를 줄이는 작업 (가지치기)