재귀(Recursion)함수란 ?

재귀 (Recursion) 함수란 특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결해나가는 함수입니다. 문제를 해결하기 위해 원래 범위의 문제에서 더 작은 범위의 하위 문제를 먼저 해결함으로써 원래 문제를 해결해 나가는 방식입니다. 일반 반복문을 통해 구현 가능한 기능은 재귀 함수를 통해 구현이 가능하며 반대로 재귀 함수로 구현 한 기능을 반복문으로 구현이 가능합니다.

재귀 함수는 함수 내에서 자기 자신을 계속 호출하는 방식이기 때문에 함수 안에 반드시 종료 구간이 되는 Base Case를 생각하며 코드를 구현해야 합니다.

.
.

백준 5639번 이진 검색 트리 문제를 풀었을 때, 익숙치 않았던 재귀함수 파트가 나와 머리가 아팠던 적이 있어 직접 간단하게 재귀함수가 어떻게 호출 -> 복귀 되는지 코드로 알아보았습니다.

import java.util.Scanner;

public class Main {
    public static void recurse(int start,int end) {         
        if(start > end) {
            System.out.println("!! recursion" + "(" + start + "," + end + ") 입니다. 함수를 return 합니다 !! ");
            return;
        }else {
            System.out.println("recursion" + "(" + start + "," + end + ") 를 호출");
            end --;
            recursion(start,end);
            System.out.println("recursion" + "(" + start + "," + end + ") 로 복귀");
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        recursion(2,n);
    }
}

< 입력 >
5
< 출력 >
recursion(2,5) 를 호출
recursion(2,4) 를 호출
recursion(2,3) 를 호출
recursion(2,2) 를 호출
!! recursion(2,1) 입니다. 함수를 return 합니다 !!
recursion(2,1) 로 복귀
recursion(2,2) 로 복귀
recursion(2,3) 로 복귀
recursion(2,4) 로 복귀

그림으로 알아보면 호출 할 함수를 Funtion(int n) 이라 했을때 다음과 같이 동작합니다.
그림은 https://lktprogrammer.tistory.com/106 에서 참고 했습니다..!