[알고리즘] 재귀

2023.1.12 작성

 

🔸 재귀함수란 

- 자기 자신을 호출하는 함수

 

🔸 재귀함수의 장점

- 불필요한 반복문 사용 안해도 돼서 코드가 쉽고 간결해짐, 수정 용의

- 변수를 여러개 사용할 필요 없음

 

🔸 재귀함수의 단점

- 코드의 흐름을 직관적으로 파악하기 어려움

- 반복하여 매서드 호출 시, 지역변수, 매개변수, 반환값 모두 process stack에 저장하여 비교적 메모리를 많이 사용함

- 메서드 종료 후 복귀 시 컨텍스트 스위칭 비용 발생

 

🔸 재귀함수 사용을 위한 조건 

-  recursive를 위한 문제 쪼개기 (재귀적 사고.. 헷갈리더라 자주해봐야함) -> recursive case

- 재귀함수 탈출/종료 조건이 필요함 -> base case

 

🔸 재귀 함수 사용이 적합한 상황 (vs 반복문)

- 문제를 비숫한 구조의 더 작은 문제로 나눌 수 있을 때

- 중첩된 반복문이 많거나 중첩 횟수를 예측하기 어려운 경우

- 변수 사용을 줄여 mutable state(변경가능한 상태)를 제거하여 프로그램 오류 발생 가능성을 줄이는 경우

 

🔸 재귀함수 템플릿

//수도코드
public type refunction(num){
    //base case
    if (탈출조건)
        return ~~ ;

    //recursive case
    return ~~ + refunction(num-1);
}

🔸 예시 -   factorial

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