재귀 호출

재귀 호출 (Recursive call)

함수 안에서 동일한 함수를 호출하는 형태
익숙해져야함

 

예제 [ 팩토리얼 ]

• 2! = 1 x 2
• 3! = 1 x 2 x 3
• 4! = 1 x 2 x 3 x 4

규칙! : n! = n x (n - 1)!

• 함수 생성
• 함수 탈출 조건 생성
  • n = 1 이면 return n
• 그게 아니면
  • return n * 함수(n - 1)

public class Factorial {
    public int factorialFunc(int n) {
        if(n <= 1) {
            return n;    // or 1
        }
        
        return n * this.factorialFunc(n - 1);
    }
}


Factorial fObject = new Factorial();
fObject.factorialFunc(5);    // 120



/* 시간 복잡도와 공간 복잡도
 * n - 1번 반복문을 호출한 것과 동일
 * 함수 호출시 지역변수 n 생성
 * 둘다 O(n - 1) 둘 다 O(n)
 */

 

 

함수는 내부적으로 스택처럼 관리됨

출처 221205_day15_재귀호출 & (tistory.com)

 

 

 

 

 

 

 

 

 

 

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스