Recursion

#Recursion

 

재귀함수는 자신을 재참조하는 함수를 일컫는다. 

 

예를 들면 Top - Bottom으로 진행되는 경우 이를 split 할 때 사용하기도 한다.

 

재귀함수에는 반드시 종료조건(기저사례)를 작성해야 한다. 그렇지 않으면 무한 루프가 발생한다.

또한

재귀함수는 사이클이 발생하는 경우에는 사용하면 안 된다. 이 경우도 동일한 이유다.

 

매개변수의 상태를 변경시켜 기저사례까지 도달하여 문제를 해결하는 경우 보통 사용한다.

 

# DP

 

DP 문제를 푸는 경우 함수의 참조가 적은 경우 재귀 함수로 문제를 해결하는 것이 더 효율적일 수 있다.

이러한 경우가 아니라면 반복문을 사용하는 것이 더 효율적이다. 

 

 

 

#예시

 

1. 팩토리얼

 

팩토리얼 n! 의미는 그 이전의 항을 모두 곱하는 것이다. 

 

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

 

해당 함수는 0!, 1! 이 1을 반환하는 특징이 기저사례로 처리되었고 이후 매개변수의 값에 -1을 한 매개변수의 상태로 재귀호출을 하여 결과를 도출한다.

 

 

 

2. 피보나치

 

 

피보나치의 점화식은 F0 =0 , F1 = 1 and Fn = Fn-1 + Fn-2 이다.

 

 

점화식(Recurrence relation)은 수열의 항들 사이의 관계를 재귀적으로 정의하는 수학적인 식입니다. 이전 항들의 값을 사용하여 다음 항의 값을 계산하는 방법을 제공합니다.

점화식은 주로 수열, 재귀 알고리즘, 동적 계획법 등의 분야에서 사용됩니다. 수열의 특정 항을 계산하거나 문제를 해결하는 데 사용될 수 있습니다. 일반적으로 다음과 같은 형태로 표현됩니다:

a_n = f(a_{n-1}, a_{n-2},..., a_{n-k})

여기서 a_n은 수열의 n번째 항이고, f는 이전 항들 a_{n-1}, a_{n-2},..., a_{n-k}을 사용하여 다음 항 a_n을 계산하는 함수 또는 식입니다. k는 점화식에서 고려되는 이전 항들의 개수를 나타냅니다.

점화식은 주어진 초기 조건과 점화식 자체에 의존하여 수열을 생성합니다. 초기 조건은 수열의 시작 부분을 정의하는 값들로, 주로 처음 몇 개의 항에 대한 값을 제공합니다. 점화식을 사용하여 초기 조건을 기반으로 나머지 항들을 계산할 수 있습니다.

 

int fibo(int n) {
    if (n == 0 || n == 1) return n;

    return fibo(n - 1) + fibo(n - 2);
}

 

 

재귀 함수를 호출할 때 함수 호출이 어느 정도 발생할지 대략 계산할 수 있어야 한다.