0주차-1. 기초 개념 : 재귀함수

재귀함수(Recursion function)란 정의 단계에 자신을 재참조하는 함수이다.

 

재귀함수의 특징

1. 전달되는 '상태'인 '매개변수'만 달라질 뿐 똑같은 일을 한다.
2. 그러다가 어떤 '상태'에 도달했을 때 종료되는 '기저 사례'가 있다.
3. 함수 호출에 대한 코스트가 크므로 반복문으로 풀 수 있으면 반복문으로 푸는게 좋다. 

큰 문제를 작은 문제로 나누어 해결할 때 사용한다.

 

재귀함수를 사용할 때 주의해야 할 점

• 기저 사례를 반드시 작성해야 한다. (안그러면 무한히 반복하므로)
• 사이클이 있다면 사용할 수 없다. ( f(a) -> f(b) -> f(a) ... 같은 이유로 무한 반복..)

 

 

 

---

Factorial

n!의 점화식

 

이 점화식을 코드로 표현하면 아래와 같다.

int factorial(int n)
{
    if (n < 2) return 1;			// 기저 사례
    return n * factorial(n - 1);
}

 

그런데 위에서 재귀함수의 특징에서 얘기한 바와 같이,

반복문으로 풀 수 있으면 반복문으로 푸는 게 좋다.

 

int factorial(int n)
{
    int ret = 1;
    for (int i = 1; i <= n; i++)
        ret *= i;
    return ret;
}

 

 

 

 

 

 

 

 

---

 

재귀함수를 만들 때는 정점과 정점의 간선이 어느정도는 상상이 되어야 한다

 

Fibonacci

출처: 위키백과

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

피보나치 수 같은 문제는 반복문으로 하면 어렵기 때문에 재귀함수로 풀어야 한다.

 

---

재귀함수는 처음에 어려울 수 있으나 도식화해서 풀어서 그려보고 그 과정을 반복하면 해결할 수 있다.