재귀 함수

재귀 함수란?

함수 내에서 자기 자신을(함수)를 계속적으로 호출하면서 풀어가는 방식

함수가 콜 되면서 최근에 자신을 부른 원래 함수가 스택에 차곡차곡 쌓이게 됨.

중요한건 처음 불려진 함수에서(스택 맨 밑에있는 메소드) return 되는 값이 최종 return 값이 된다.

 

즉, 어떤 수 n을 선언했을 때, n부터 쭉 타고 들어가서 가장 작은 수까지 들어간 다음에

가장 작은 수가 해결이 되면 다시 값을 거슬러 올라가면서 계산을 해서 n!의 값을 반환한다.

 

 

팩토리얼 예제

 

public static int factorial(int n) {
		
    if(n == 1) { return 1; }
	
    return n * factorial(n-1);
    
    // n! = n * factorial(n-1)
    // 4! = 4 * 3!
    // 3! = 3 * 2!
    // 2! = 2 * 1!
    // 1! --------> if문 실행
    
    // 즉 제일 작은 단위까지 들어가서 확인하고,
    // 확인이 완료되면 다시 거슬러 올라오면서 값을 계산하는 방식
    
}

 

 

피보나치 수열 예제

 

public static int fibonacci(int n) {
		
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
    
    // 구하고자 하는 값의 한 칸 앞의 값 + 두 칸 앞의 값 
    // n = (n-1) + (n-2)
    // fibonacci(5) = fibonacci(4) + fibonacci(3)
	
}