재귀함수란? (Recursion)

함수가 직접 또는 간접적으로 자신을 호출하는 프로세스를 재귀함수라고 합니다

재귀 알고리즘을 이용하면 복잡한 문제들도 간단하게 해결할 수 있습니다

반복문도 마찬가지지만 재귀함수도 종료지점을 제대로 생각하지 않고 구현을 하면 스택오버플로우가 발생할 수 있으니 항시 주의해서 구현을 해줘야합니다

 

'재귀 함수를 사용하는 이유'

 

재귀 함수는 for, while을 사용한 반복문(iteration)으로 변경할 수 있고, 반대로 for, while을 사용한 반복문을 재귀 함수로 표현할 수 도 있는데요. 

재귀 함수는 위에서 언급한 것처럼 잘못 사용하면 무한루프에 빠져 스택오버플로우를 발생시킬 수도 있고, 무한루프에 빠지지 않더라도 함수가 계속 호출되면서 함수의 매개변수, 지역변수, 리턴 값 함수 종료 후 돌아가는 위치가 스택 메모리에 저장되면서 stack이 쌓여 결국 마찬가지로 스택오버플로우를 발생시킬 수도 있습니다.

(메모리를 많이 차지하며, 성능이 반복문에 비해서 느리다고 하는 이유입니다.)

 

 

'이러한 단점을 가진 재귀 함수를 구현해서 사용한다면 그 이유는 무엇일까요?'

 

'첫 번째'로 재귀 함수의 장점은 경우에 따라 가독성을 높일 수 있다는 것입니다.

알고리즘 자체가 재귀적인 표현이 자연스러운 경우에는 재귀 함수를 쓰는 것이 가독성이 높습니다. 위에서 예로 든 피보나치 수열이나 팩토리얼 같은 경우 알고리즘을 기술한 그대로를 가지고 코드로 표현할 수 있기 때문에 for문보다 더 직관적으로 코드를 이해할 수 있습니다.

 

'두 번째'는 변수의 사용을 줄여준다는 것입니다.

변수의 사용을 줄여준다는 것은 변수가 저장되는 메모리에 대한 이야기가 아니라 'mutable state(변경 가능한 상태)'를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄여준다는 이야기이며, 이는 변수의 수를 줄이는 것뿐만 아니라 변수가 가질 수 있는 값의 종류 또는 범위도 제한하게 되어 함수를 단순하게 만들고, 불변적으로 유지될 수 있도록 합니다.

 

 

 

public class _31
{
    public static void main(String[] args)
    {
    	int N= 5;
    	
        System.out.println("1부터"+ N+"까지의 합은 : " + Function(N));
    }
    public static int Function(int num)
    {
        if(num == 1)
        {
            return 1;
        }
        else
        {
            return num + Function(num -1);
        }
    }
}

출력값

1부터5까지의 합은 : 15

 

 

팩토리얼 재귀함수

import java.util.Scanner;

public class _31
{
    public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int num = scan.nextInt();
		
		System.out.println(Factorial(num));
    }
    
    
    public static int Factorial(int n) {
    	
    	if(n==0) {
    		return 1;
    	}
    	if(n==1) {
    		return 1;
    	}
    	else {
    		return n * Factorial(n-1);
    	}
    }
}

출력값

5
120

 

 

추가 설명 링크

https://lts0606.tistory.com/509