재귀 알고리즘

재귀 함수

참고 링크

https://blog.encrypted.gg/943?category=773649

[실전 알고리즘] 0x0B강 - 재귀

https://imjeongwoo.tistory.com/17

[알고리즘] 재귀(Recursion)와 수학적 귀납법(Mathematical Induction)

 

 

: 종료 조건(base condition, base case)에 도달할 때까지 자기 자신을 호출하며 반복하는 함수

 

 

ex) 팩토리얼

public static int factorial(int N){
    if (N<=1) return 1; //base condition
    return N * factorial(N-1); //base condition에 다다를 때까지 해당 출력 반복
}

 

 

1. 절차적으로 이해하기 (코드 흐름 따라가기)

호출 결과를 쌓아가다가(stack 방식) 종료 시 마지막 출력값부터 계산 시작

//N=5일 때
factorial(5){ 
    return 5 * factorial(4){ //4단계
      return 4 * factorial(3) { //3단계
        return 3 * factorial(2){ //2단계
         return 2 * 1; //계산 1단계
        }
      }
    }
}

 

 

=> 코드가 복잡하고 길어질수록 절차적으로 증명하기 어려워짐

=>

2. 귀납적으로 이해하기

 

//N=5일 때

(1) N=1일 때 1이 출력됨 (base condition, 자명한 조건)

(2) factorial(N)일 때 N * factorial(N-1) 출력 (참으로 가정)

(3) 1번과 2번이 참이므로 1부터 5까지 return문을 반복한다 ex. 1 * 2 *  .. * 5 (증명하기)
     => 결국 N에서 base condition으로 수렴

 

 

 

 

• 특징

1. 무한 루프로 인한 런타임 에러가 발생하지 않도록 종료 조건(base condition) 필요

모든 입력은 base condition으로 수렴함

 

2. 함수 명확히 정의해야 함

함수의 인자값, 호출 결과값을 명확히 인지하며 작성해야 함

 

3. 모든 재귀 함수는 반복문 처리 가능

N 값이 커질수록 호출되는 함수량이 많아져 메모리, 시간 측면에서 비효율적일 수 있음

이때 반복문 또는 DP(Dynamic Programming) 사용 권장됨