[알고리즘] 재귀

재귀는 알고리즘이 아님!

-> 재귀는 for문과 같은 단순한 프로그래밍 작성 방법

 

재귀는 크게, 선형 재귀와 비선형 재귀로 나뉨

선형 재귀는 한 번 호출에 자신을 한 번 부름 -> Linear한 결과를 도출할 수 있음

비선형 재귀는 한 번의 호출에 자신을 여러 번 부름  

 

재귀 기본

recursive() {
    // basis part
    if () { return }; // 재귀(가지)의 끝을 알림, 종료 조건

    // inductive part
    recursive(); // 재귀 호출
}

 

-> 함수 내에서 자기 자신을 한 번 호출하므로 선형 재귀라고 할 수 있음

 

 

 

 

비선형 재귀 횟수 구하기

- 출력 횟수 : 갈래(한 번 호출마다 자신을 부르는 횟수) ^ 반복 횟수

 

 

- 예제 코드

public class Recursive {
	static int[] arr = {1, 3, 5};
	static int answer = 0;
	
	public static void main(String[] args) {
		recursive(0, 1);
	}

	private static void recursive(int idx, int val) {
		// basis part
		if (idx == arr.length) {
			System.out.println(val);
			return;
		}
		
		// inductive part 
		recursive(idx + 1, val + arr[idx]);
		
		// inductive part 
		recursive(idx + 1, val * arr[idx]);
	}
}

자신을 2회 호출하므로 비선형 재귀

 

 

- 결과

 

10

25

11

30

9

20

8

15

 

갈래(함수 내에서 자신을 부르는 횟수)가 2회이고, 총 3번 반복하므로,

$2^3$개의 결과가 출력됨