재귀(Recursion)함수란?
특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결해나가는 함수
문제를 해결하기 위해 원래 범위의 문제에서 더 작은 범위의 하위 문제를 먼저 해결함으로써 원래 문제를 해결해 나가는 방식
재귀함수의 무한 루프
재귀함수는 함수 내에서 자기 자신을 계속 호출하기 때문에 함수 안에 반드시 종료 구간이 되는 Base Case를 생각하며 코드를 작성해야함
public class Test{
public static void main(String[] args){
recursion_test();
}
public static void recursion_test(){
System.out.println("안녕하세요");
recursion_test();
}
}recursion_test라는 Method를 보면 "안녕하세요"를 출력하고 다시 자기 자신 recursion_test를 호출하고 있음
하지만 해당 소스에는 자기 자신을 호출만 하고있지 함수 영역이 종료되는 구간이 없기때문에 "안녕하세요"를 계속 출력하는 무한루프에 빠지게 됨
재귀함수를 사용하는 이유?
재귀함수는 for, while문으로 변경될 수 있고, 반대로 for, while문 또한 재귀함수로 표현할 수 있음
위 예제 코드처럼 재귀함수를 잘못 사용하여 무한루프에 빠지거나, 무한루프에 빠지지 않더라도 함수가 계속 호출되면서 스택이 쌓여 스택오버플로우를 발생시킬 수도 있음
(재귀가 메모리를 많이 차지하며 성능이 반복문에 비해 느리다고 말하는 이유)
이러한 단점을 가졌는데도 재귀를 사용하는 이유가 대체 뭘까?
재귀함수는 경우에 따라 가독성을 높일 수 있음
: 알고리즘 자체가 재귀적인 표현이 자연스러운 경우 재귀함수를 쓰는 것이 더 가독성이 높음
예를 들어, 피보나치 수열이나 팩토리얼 같은 경우 알고리즘을 기술한 그대로를 가지고 코드로 표현할 수 있어서 for문보다 더 직관적으로 코드 이해가 가능
변수의 사용을 줄여줌
: 변수의 사용을 줄인다는 것은 메모리에 관한 사항이 아니라 변수의 변경 가능한 상태를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄여준다는 이야기임
이는 변수의 수를 줄이는 것뿐만아니라 변수가 가질 수 있는 값의 종류 또는 범위도 제한하게 되어 함수를 단순하게 만들고 불변적으로 유지할 수 있도록 함
재귀함수 코드 구현
public class Test{
public static void main(String[] args){
recursion_test(5);
}
public static void recursion_test(int num){
if(num==0){ return; }
else{
System.out.println("안녕하세요");
recursion_test(num-1);
}
}
}recursion_test는 매개변수 num을 받고 if 구문에 의해 분기되고있다.
매개변수 값이 0일 경우 return을 하고 0이 아닐 경우 "안녕하세요"를 출력하고 num-1에 해당하는 값을 매개변수로 가지고 다시 recursion_test 메소드로 들어간다
num값이 0일 경우, return을 하게 되는 구문이 이 재귀함수의 Base Case구간이 된다.
1부터 n까지 합 구하기
public class recursion_test2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
System.out.printf("1부터 %d까지 합 : %d", num, recursion(num));
}
private static int recursion(int num) {
if(num == 1) return 1;
else return num + recursion(num-1);
}
}num이 1이면 그냥 1을 리턴하고 함수가 종료
1이 아닐 경우, 현재 num값에 recursion(num-1)결과로 리턴되는 값을 더하여 리턴
참고
https://wildeveloperetrain.tistory.com/116
https://lktprogrammer.tistory.com/106
https://itstudy402.tistory.com/36
