[자료구조] 재귀함수(Recursion Function)

* 재귀함수

 1. 재귀란?

  -. 자기 자신에게 되돌리는 것

 

 2. 재귀함수란? 

  -. 하나의 함수안에서 자신의 함수를 다시 호출하는 함수

  -. 재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용 

  -. 재귀함수는 자신의 로직을 반복하다가 함수의 탈출조건이 만족되면 함수 종료 후 결과 도출

  -. 반드시 탈출조건이 명시되어있어야 함(함수가 호출되면 함수를 위한 메모리 공간이 할당되기때문에 재귀함수의 탈출조건을 명시하지 않으면 무한반복이 되고 스택 오버플로우 발생하게 됨)

 

 3. 재귀함수의 특성

   -. 1 > 2 > 3 > 4 순으로 호출되어 4 > 3 > 2 > 1 순으로 종료되는 특성을 가짐

 

 4. 재귀함수 예시

   -. 탈출조건이 명시된 간단한 재귀함수 예시

---

       void RecursiveFunc(int num)

       {

           if(num <= 0) return; // 탈출조건

           printf("Recursive call! %d\n", num);

           RecursiveFunc(num -1);

        }

       int main(void)

       {

           RecursiveFunc(4);

           return 0;

        }

 

        [실행결과]

        Recursive call! 4 

        Recursive call! 3

        Recursive call! 2

        Recursive call! 1

---

 

 5. 재귀함수의 활용

   -.  팩토리얼(n!) 

   > n! = n x (n -1) x (n - 2) x ··· x  2 x 1

   > n! = n x (n -1)!

   -. 팩토리얼 재귀적 함수 구현

---

       int FactorialFun(int n)

       {

            if(n == 0) return 1;

            else return n * FactorialFun(n -1);

        }

        int main(void)

       {

            printf("1! = %d \n", FactorialFun(1));

            printf("2! = %d \n", FactorialFun(2));

            printf("3! = %d \n", FactorialFun(3));

            printf("4! = %d \n", FactorialFun(4));

            printf("5! = %d \n", FactorialFun(5));

            return 0;

        }

       [실행결과]

       1! = 1

       2! = 2

       3! = 6

       4! = 24

       5! = 120

---

   -. 피보나치 수열

    >  0, 1, 1, 2, 3, 5, 8, 13, 21 ...

    > 앞수 두개를 더한 값으로 현재값을 만들어가는 수열

 

       int fibo(int n)

       {

            if(n == 1) return 0;

            else if(n == 2) return 1;

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

       }

       int main(void)

      {

            printf("1번째 피보나치 수열의 값 : %d\n", fibo(1));

            printf("2번째 피보나치 수열의 값 : %d\n", fibo(2));

            printf("5번째 피보나치 수열의 값 : %d\n", fibo(5));

            printf("10번째 피보나치 수열의 값 : %d\n", fibo(10));

           return 0;

       }

      [실행결과]

      1번째 피보나치 수열의 값 : 0

      2번째 피보나치 수열의 값 : 1

      5번째 피보나치 수열의 값 : 3

      10번째 피보나치 수열의 값 : 34

---