[Java] 재귀함수

재귀함수

• 함수가 직접 또는 간접적으로 자신을 호출 하는 프로세스다. 
• for, while 반복문과 비슷한 기능이라고 볼 수 있다.

	public int factorial(int num){

    if ( num == 0 ) return 1;  // num 이 0일 경우 1 리턴하고 종료!
  
    return num * factorial(num-1);  // factorial 메서드 안에 num 을 1씩 줄여가며 본인 메서드 호출
  }

---

  public int fibonacci(int num){
  
  	// 피보나치 수열 a(n) = a(n-1) + a(n-2) 반복된다. ex) 0, 1, 1, 2, 3, 5, 8, 13
    if ( num == 0 ) return 0;  // 앞에 숫자 2개가 존재해야 하므로 선언 또는 해당 값일 때 종료
    if ( num == 1 ) return 1;  // 앞에 숫자 2개가 존재해야 하므로 선언 또는 해당 값일 때 종료

    return fibonacci(num-1) + fibonacci(num-2); // 본인 메서드 호출

장점 

• 변수를 여러개 만들 필요가 없다. 
• 반복문을 사용하지 않기 때문에 코드가 간결하다. 

 

단점

• 지속적으로 호출하면 지역변수,매개변수, 반환값을 stack에 저장하기 때문에 StackOverflowError가 발생할 수 있다.
• 함수 호출 -> 복귀를 위한 컨텍스트 스위칭에 비용이 발생한다. 

 

대표적인 사용 예제

팩토리얼 (Factorial), 피보나치 수열 (Fibonacci) 에 사용.