재귀 용법 (recursive call)

1. 재귀 용법

함수 안에서 동일한 함수를 호출하는 형태

코드 작성 패턴을 익히자

 

2. 예제

n! = n x (n - 1)!

import java.util.*;

public class RecursiveCall {
    public static void recursiveCall() {
        for (int i = 1; i < 10; i++) {
            System.out.println(factorial(i));
        }
        
    }
    
    public Integer factorial(Integer num) {
    	if (num > 1) {
            return factorial(num - 1);
        } else {
            return num;
        }
    }
}

    public Integer factorial(Integer num) {
    	if (num <= 1) {
            return num;
        }
        return factorial(num - 1);
    }

시간복잡도 O(n)

공간복잡도 O(n)

 

3. 재귀 호출의 일반적인 형태

fun(입력) {
    if (입력 > 일정값) {
    	return fun(입력 - 1);
    } else {
    	return 일정값, 입력값, 또는 특정값;
    }
}

fun(입력) {
    if (입력 <= 일정값) {
    	return 일정값, 입력값 또는 특정값;
    } 
    fun(입력보다 작은 값);
    return 결과값;
}

 

4. 연습

import java.util.*;

public class RecursiveCall {
    public static void recursiveCall() {
        for (int i = 1; i < 10; i++) {
            System.out.println(multiple(i));
        }
    }
    
    // 1. 1부터 num까지의 곱이 출력
    public Integer multiple(Integer num) {
    	if (num <= 1) {
            return num;
        } else {
            return num * multiple(num - 1);
        }
    }
}