[알고리즘] 재귀 (Recursive)

개념

재귀 함수 (Recursive)

• 함수 안에 자신의 함수를 다시 호출하는 함수를 의미.

• 함수 실행은 스택에 저장되는데 이 때 스택 오버 플로우를 주의해야 한다.

• 재귀함수는일반적인 수학의 점화식을 그대로 표현가능한 능력을 가지고있어 프랙탈, 분할반복등에서 엄청난 효율을 보여준다.

• 변수가 줄어들고 코드가 간결해지지만, 메모리를 더 사용할 수 있다.

구현 방법

• 재귀 함수 호출을 상단에 두는 방법

#include <iostream>
using namespace std;

int function(int input) {
    if (input > 일정값) {  // 입력이 일정 값 이상이면
        return function(input - 1);  // 입력보다 작은 값을 사용해 재귀 호출
    } else {
        return 일정값;  // 재귀 호출 종료 시 반환 값
    }
}

int main() {
    int 입력 = 5;  // 예시 입력값
    int 결과값 = function(입력);
    cout << "결과값: " << 결과값 << endl;
    return 0;
}

• 재귀 함수 호출을 하단에 두는 방법

#include <iostream>
using namespace std;

int function(int input) {
    if (input <= 일정값) {  // 입력이 일정 값보다 작거나 같으면
        return 일정값;  // 재귀 호출 종료 시 반환 값
    }
    function(input - 1);  // 입력보다 작은 값을 사용해 재귀 호출
    return 결과값;  // 마지막에 반환할 결과값
}

int main() {
    int 입력 = 5;  // 예시 입력값
    int 결과값 = function(입력);
    cout << "결과값: " << 결과값 << endl;
    return 0;
}

꼬리 재귀

• 재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반환 되도록 하는 방법.

• 스택 오버 플로우 문제를 해결하는 방법이다.

#include <iostream>

int factorial(int input, int result = 1) {
	if (input == 1) {
		return result;
	}
	return factorial(input - 1, input * result);
}

int main() {
	std::cout << factorial(5);
	// result가 처음엔 입력이 없어서 1로 초기화 된다. 
	// 이후 재귀할 땐 입력된 값으로 초기화가 된다.
}