재귀 함수

재귀 함수

Recursion Function

---

 

 재귀 함수란 자기 자신과 같은 메소드를 계속 호출하는 함수를 말한다.

 재귀 함수는 무한 루프를 방지하기 위해 적어도 하나의 base case (기저 조건) 가 존재해야 한다. 따라서 모든 함수는 결국 base case에 수렴해야 한다.

 

 

재귀 함수의 장점

1. 가독성이 좋다.

 기본적으로 재귀 함수는 모두 반복문으로 표현할 수 있다. 그러나 알고리즘 자체가 재귀적인 표현이 자연스러운 경우 재귀 함수를 쓰는 것이 코드량과 변수가 줄어들어 가독성이 향상된다.

•  ex) 피보나치 수열

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

 

2. 변수 사용을 줄여준다.

 변수 사용을 줄여준다는 것은 단순히 메모리 사용 측면의 이야기가 아니다. mutable state를 제거하여 프로그램에 오류가 생길 수 있는 가능성을 줄인다는 것이다. 

 

 

재귀 함수의 단점

1. 메모리를 많이 차지한다.

 재귀 함수는 반복적으로 자기 자신을 호출하면서 stack에 쌓이기 때문에 메모리를 많이 차지한다. 메모리 공간을 계속 이용하기 때문에 메모리의 제한이 있거나 무한 재귀가 일어날 경우 stack overflow가 발생해 프로그램이 비정상 종료된다.

 

 

 

 

 

참고

https://velog.io/@gillog/Algorithm-%EC%9E%AC%EA%B7%80%EC%99%80-%EB%B0%98%EB%B3%B5%EB%AC%B8

https://medium.com/sjk5766/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A5%BC-%EC%93%B0%EB%8A%94-%EC%9D%B4%EC%9C%A0-ed7c37d01ee0