[알고리즘] 재귀 함수(Recursive Function)

 

 

 

재귀 함수란?

• 함수 내에서 자신을 다시 호출하여 반복 작업을 수행하는 방식의 함수
• 함수 내에 같은 이름의 함수가 오는 것

 

 

 

재귀 함수(알고리즘)의 조건

• 무한 루프로 인해 stackoverflow가 되는 것을 방지하기 위해 종료 조건을 꼭 포함해야 된다.

 

 

 

기본 구성

• Basecase : 종료 조건
• Recursive case : 자신을 호출하는 함수를 포함하는 부분

 

 

 

재귀 함수를 이용할 수 있는 유형

• Factorial (팩토리얼, n!)
• X의 n승 구하기
• 피보나치 수열
• 유클리드 호제법 (최대공약수)

 

 

 

장점

• 코드 길이와 변수가 적어져서 가독성이 높아진다.
• 변수 사용을 줄여 준다. (mutable state를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄여준다.)

 

 

 

단점

• 메모리를 많이 차지한다. (함수를 반복적으로 호출하여 스택의 메모리가 커지고, 호출하는 횟수가 많아지면 stackoverflow가 발생할 수 있다.)
• 시간이 오래 걸린다.

 

 

 

JAVA예제(팩토리얼)

public class Factorial {

	public static void main(String[] args) {
		int input = 4;
		
		System.out.println(fact(input));

	}
	
	public static int fact(int n) {
		if(n<=1)
			return n;
		else
			return fact(n-1)*n;
	}

}

 

 

 

 

 

 

 

참조 : https://velog.io/@jyebe/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98Recursive-Method  /  https://marobiana.tistory.com/79