재귀 알고리즘에 대해 알아보자!

재귀 알고리즘이란?

• 재귀 알고리즘은 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘이다.
• 재귀 함수는 반복문(for, while문)으로도 충분히 대체 가능하다.
• 재귀 함수는 언제 사용할까?
  - 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
  - 반복문이 많이 중첩되거나 중첩 횟수를 예측하기 어려운 경우
  - 변수의 사용을 줄여 메모리를 비교적 간소화하고 프로그램 오류가 발생할 가능성을 줄이고자 하는 경우
  
  - 단, 재귀함수가 모든 경우에서 반복문보다 좋은 것은 아니다.
  
  
• 대표적인 예로는 피보나치 수열, 팩토리얼 계산, 탐색 트리의 순회 등이 있다.

---

재귀 알고리즘의 사용

 

1. 피보나치 수열

• 피보나치 수열이란,
  F(0) = 0
  F(1) = 1
  F(2) = F(0) + F(1)
  F(3) = F(1) + F(2)
  .
  .
  F(n) = F(n-2) + F(n-1)
  이런 식의 수열을 말한다.

 

• 피보나치 수열에 대한 문제가 프로그래머스에 있어서 재귀함수와 반복문으로 각각 문제를 풀어보았습니다.
  
  - 문제에서 n번째 피보나치 수를 1234567로 나눈 나머지를 리턴하라고 합니다.

<재귀함수 사용>

public int solution(int n)
    {
        dicFib = new Dictionary<int, long>();

        long answer = 0;

        answer = Fibonacci(n);

        return (int)answer;
    }
public long Fibonacci(int n)
    {
        if (dicFib.ContainsKey(n))
            return dicFib[n];

        if (n <= 1)
        {
            dicFib.Add(n, n);
            return n;
        }

        long num1 = Fibonacci(n - 2);
        long num2 = Fibonacci(n - 1);

        long result = (num1 + num2)%1234567;

        dicFib.Add(n, result);

        return result;
    }

< 결과 - 테스트 코드 >

 

< 결과 - 제출 후 채점 >

<반복문 사용>

public int solution(int n)
    {
       if(n==0 || n==1)
            return n;
        
        int answer=0;
        int f1=1;
        int f2=0;
       
        for(int i=2;i<=n;i++)
        {
            answer= (f1+f2) % 1234567;
            f2=f1;
            f1=answer;           
        }

        return answer;
    }

 

<결과 - 테스트 코드>

 

<결과 - 제출 후 채점>

 

• 결론: 해당 문제에서는 재귀함수를 사용하지 않고 반복문을 활용하는 것이 시간 효율이 더욱 좋게 나왔습니다. 그러기에 상황에 따라 재귀함수와 반복문 중 어느 것을 사용할지 고려하는 것이 맞다고 봅니다.

 

2. 팩토리얼 계산

• 팩토리얼은 수학에서 "n!"로 표기되며, 실제 계산은 n*(n-1)*(n-2)* ... *1의 값을 가진다.
  예를들어 5! 이면 5*4*3*2*1 = 120이 5! 의 계산값이다.
  
  

 

<재귀함수>

public int Factorial(int n)
    {
        if (n <= 1)
        {
            return 1;
        }
        
        return n * Factorial(n - 1);
    }

 

<반복문>

public int Factorial(int n)
    {
        int num = n;

        while (n > 1)
        {
            n--;

            num *= n;
        }

        return num;
    }

---