안녕하세요~

오늘은 재귀 알고리즘에 대해서 알아보겠습니다!

재귀 알고리즘이란?

재귀 : 어떠한 것을 정의할 때 자기 자신을 참조하는 것. [from 위키..]
즉, IT 관점에서 본다면 자기 자신을 계속해서 호출하는 알고리즘입니다.

위 그림과 같이
  1. main() 메소드 안에서 최초 recurse() 메소드 호출
  2. 호출된 recurse()에서 자기자신인 recurse() 호출
  3. 종료되기까지 계속해서 자기자신 호출 반복
이 처럼 계속해서 자기자신을 호출하는 방식의 알고리즘입니다.

해당 알고리즘을 적용한 재귀함수를 많이 쓴다고 해요~

왜 재귀 함수를 쓰는가?

어? 반복문과 비슷한데 왜 재귀 알고리즘을 쓰나요?

재귀 함수의 장점은 “가독성”  이 가장 크다고 생각해요.
인터넷 찾아보면 변수 사용을 줄인다는 장점도 있는데,
결국에는 그것도 가독성이죠… 하하..

저 같은 경우 폴더-파일 구조를 for문이나 while문 등의 반복문을 통해 구현하기 어렵다고 느꼈어요.
반복문을 사용하게 되면 그 만큼의 가독성도 떨어지고 변수도 많이 사용하더라구요..
그래서 재귀 함수를 통해 구현을 한번 해본 적이 있는데 이때 엄청 간단하게 구현을 해냈습니다..!!

하지만 재귀함수는 메모리 사용량이 많고, 단순 반복문보다 성능이 더 떨어질 수 있는 단점이 있어요.

그리고 종료 조건을 잘못 했을때에는 Stack Overflow 발생..

그래서 특히 재귀 함수의 경우에는 주의해서 사용해야합니다!

재귀 알고리즘 예시 (팩토리얼)

재귀 알고리즘 검색 시에 가장 많이 나오는 팩토리얼 구하기입니다.

팩토리얼은 특정 정수에서 1까지의 수를 모두 곱하는 것이에요.
예를 들어서 4! = 4 x 3 x 2 x 1 = 24.  [즉 4! = 24]

자. 그러면 팩토리얼을 구현한 코드를 보시죠!

public static void main(String[] args) {
  System.out.println(factorial(4));
}

public static int factorial(int n) {
  int result = 1;
  for (int i=n ; i>=1 ; i--) {
    result *= i;
  }
  return result;
}

1. main()메소드 실행
2. factorial(4) 실행
3. n = 4, n * factorial(n-1) 실행
4. n = 3, n * factorial(n-1) 실행
5. n = 2, n * factorial(n-1) 실행
6. n = 1, if문안의 return 1 실행

결과는 4 * 3 * 2 * 1 = 24 가 나옵니다!

그냥 for문을 통한 반복문으로 실행한다면?

public static void main(String[] args) {
  System.out.println(factorial(4));
}

public static int factorial(int n) {
  int result = 1;
  for (int i=n ; i>=1 ; i--) {
    result *= i;
  }
  return result;
}

반복문을 통해 구현한 팩토리얼도 똑같이 24의 결과값이 나옵니다.
그런데 사실 반복문으로 구현하나, 재귀함수를 통해 구현하나 비슷해보입니다.
하지만… 팩토리얼이 아닌 더 복잡한 프로그램을 구현하려 한다면 어떻게 될까요?
더욱 더 복잡하고, 가독성도 그 만큼 떨어지게 될거에요.. (제 생각 ㅎ)

마치며.. 결론은?

항상 재귀 함수가 좋지는 않습니다!
고려해봐야 할 부분도 일반 반복문보다 훨씬 많고,
많이 쓰지 않는다면 그 만큼 어려운 알고리즘이라고 생각해요..
하지만? 적용할 수 있는 상황에서 적용을 한번 해본다면
아!! 왜 써야하겠구나..! 라는 거를 깨달을테니 한번 도전해봅시다!

상황에 맞게 적절히 골라 사용을 해보며 공부해봅시다!

오늘도 제 글을 봐주셔서 감사합니다 ^__^