4.Recursive Function 재귀함수

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
/*
 * Recursive FUnction(재귀함수)
 * 
 * 어떠한 함수 정의 내에서 자기 자신 함수 호출
 * ex)
 * void f()
 * {  
 *  .....
 *  f();
 *  .....
 * }
 * 
 * 분할 정복(divide & conquer) 방식의 문제해결기법
 * n개의 문제 -> 1개의 문제 + (n-1)개으 ㅣ문제 
 * n개의 문제 -> n/2개의 문제 + n/2개의 문제
 * n개의 문제 -> n/4개의 문제 + n/4개의 문제+ n/4개의 문제 +n/4개의 문제
 * 
 * 단점: 속도 느림 / 기억장소 소비 많음
 * 장점: 알고리즘을 작성하거나 이해하기 쉬움
 * 
 * 강의 목적: 재귀함수 소개 + 자동 할당 메카니즘 이해
 * 
 * Fibonacci Sequence - 피보나치 수열
 * 
 *   1    1    2    3    5    8    13    21 .....
 *   f0  f1   f2   f3   f4   f5    f6    
 *   
 * f(n) 의 정의 
 * f(n) = f(n-1) + f(n-2) when n  >= 2  n이 2 이상일때 가능
 * f(1) = 1 when n = 1
 * f(0) = 1 when n = 0
 * boundary condition 는 위의 조건처럼 recursive function이 무한 루프의 빠지지 않게 하기 위한것이다

 * 자동할당 메카니즘 이해 
 * 프로그램의 빠르기 척도
 * complexity : O(1)[오덜오브원 딱 그만큼의 시간] 
 *              O(log(n))[오덜오브 로그 엔 로그엔만큼의 시간이 소요]
 *              O(n) [오덜오브 엔 데이터의 갯수의 비례하여 선형적으로 증가한다.]      
 *              O(n+log(n))[오덜오브 엔 로그엔]
 *              O(n*n)[오덜오브 엔 스쿼어 급격한 증가]
 * 
 * time complextiy: O(n*n) 
 * space compleity: O(n)
 */

namespace Fibo
{
    
    class Program
    {
        static int fibo(int n)
        {
            if (n == 0) return 1;
            if (n == 1) return 0;
            if (n < 0)
            {
                Console.WriteLine("Unexpectde minus argument!!");
                Environment.Exit(-1);
                return -1;
            }
            int f0 = 1;
            int f1 = 1;
            int f2 = 0;
            for (int i = 1; i < n; i++)
            {
                f2 = f1 + f0;
                f0 = f1;
                f1 = f2;
            }
            return f2;
        }

        static int fiboRF(int n)
        {
            if (n == 0) return 1;
            if (n == 1) return 0;
            if (n >= 2) return fiboRF(n - 1) + fiboRF(n - 2); //함수호출 하나에서 2개로 분리되서 매우 비효율적이라서 그렇다
            Console.WriteLine("Unexpectde minus argument!!");
            Environment.Exit(-1);
            return -1;
        }

        static void f(int n)
        {
            //Recursive Function에는 반드시 아규먼트가 존재한다.
            if (n == 0) return;
            Console.WriteLine("hello");
            f(n-1);
        }

        static void Main(string[] args)
        {
           // f(5)
            
            for (int i = 0; i < 44; i++) //프로그램이 비효율적이라서 속도가 느리다. 
            {
                Console.WriteLine(fibo(i));
                //Console.WriteLine(fiboRF(i));
                //굳이 재귀함수사용안해도 되지만 소개하기 위해 사용
                //다음시간에는 재귀함수의 자동할당 메카니즘 대해 배울것이다.
            }
        }
    }
}