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

Jinga·2023년 3월 13일
1

알고리즘-이론

목록 보기
2/5
post-thumbnail

재귀 함수(Recursive Function)란?

재귀함수란, 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다.
즉, 함수 정의 내에 같은 이름의 함수가 올 때 이를 재귀함수라 한다.
def를 통해 함수f(x)를 만들고, 만든 함수f(x) 안에서 다시 그 함수f(x)를 호출하는 것이다.

재귀 함수 예시

재귀함수 사용시 반드시 탈출 조건이 있어야 stack overflow를 방지할 수 있다.
간단한 예시를 살펴보자.

```
def rf(num):
    if num == 0:
        break
    else:
        print(num)
        rf(num-1)
rf(5)
```
# 출력 결과
5
4
3
2
1
'function(0)'은 탈출 조건을 만나서 실행이 멈추고 이전함수인 'function(1)'로 복귀한다.
'function(1)'의 나머지 코드인 print(1)가 실행되고 이전함수인 'function(2)'로 복귀한다.
'function(2)'의 나머지 코드인 print(2)가 실행되고 이전함수인 'function(3)'로 복귀한다.
'function(3)'의 나머지 코드인 print(3)가 실행되고 이전함수인 'function(3)'로 복귀한다.
'function(4)'의 나머지 코드인 print(4)가 실행되고 이전함수인 'function(3)'로 복귀한다.
'function(5)'의 나머지 코드인 print(5)가 실행되고 자신을 호출한 곳으로 돌아간다.

팩토리얼, 유클리드 호제법(최대공약수 계산)예제도 검색해서 직접 작성해보자.

재귀 함수의 장점

  1. 변수를 많이 만들지 않아도 된다.
    예를들어 현재 상태를 저장해야 할 경우 tmp 변수를 만들기보다
    상태를 메서드를 재귀적으로 호출하면서
    변경된 상태를 전달 함으로써 변수의 수를 줄일 수 있습니다.
    1. while문이나 for문같은 반복문을 사용하지 않아도 되기에
      코드가 간결해집니다

재귀 함수의 단점

  1. 지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환값을
    모두 process stack에 저장해야한다.
    이런 과정은 선언한 변수의 값만 사용하는 반복문에 비해서
    메모리를 더 많이 사용하게 되고, 이는 속도 저하로 이어진다.
    1. 함수 호출 -> 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 된다

재귀함수의 단점 해결 방법 - 꼬리 재귀(tail call recursion)

재귀 함수의 가장 큰 문제가 자신을 호출한 뒤 결과를 기다리면서
생기는 콜스택의 부하로 인한 메모리 낭비였는데,
꼬리 재귀라는 개념을 이용하면 재귀 호출이 끝나는 시점에서 아무 일도
하지 않고 바로 결과를 반환하도록 하는 방법으로 함수의 상태 유지 및
추가 연산을 하지 않기에 스택 오버 플로우 해결할 수 있다.

# 기존 재귀함수 factorial과 꼬리재귀 factorial 함수
# Basic Recursion
int factorial(int n, int total) {
    if (n === 1) {
        return 1;
    }
    return n * factorial(n-1);
}
# Tail Recursion
int factorial(int n, total) {
    if (n === 1) {
        return 1;
    }
    return factorial(n - 1, n * total);
}
```    차이점을 잘 보면 반환부분 코드가 달라졌다. 
    꼬리 재귀의 핵심은 반환부에 연산이 없어야 한다는 점이다.
    이렇게 반환부에 연산이 없도록 구현을 한다면 컴파일러는 꼬리 재귀 최적화를
    지원하여 자체적으로 재귀함수를 해석해서 반복문으로 변경해서 실행한다.

재귀함수 백준문제

재귀의 귀재(브론즈2)

https://www.acmicpc.net/problem/25501

별 찍기 -10(골드5)

https://www.acmicpc.net/problem/2447
profile
다크모드가 보기 좋아요

0개의 댓글