[CS study] 1. 재귀와 반복

알고리즘 문제를 풀면서 가장 기본적이고, 많이 이용하게 되는 반복과 재귀에 대해서 알아보자.

반복

우리가 보통 사용하는 while문이나 for문등을 통해서 명령의 반복적인 실행을 통해 로직을 구성하고, 해결하는 것을 말한다.

재귀와 비교했을때 일반적으로는 속도가 더 빠르고, 스텍 메모리를 사용하지 않는다는 장점이 있다.

다만 무한루프가 생기는 경우에 CPU사이클이 반복적으로 사용된다는 문제가 발생한다.

재귀

재귀는 함수 자기자신을 다시 호출하여 수행하는 형태의 로직을 말한다.

즉, 큰 문제를 풀기 위해서 동일한 구조의 작은 문제로 분할하여 해결한다.

반복문보다는 속도가 느릴 수 있고(알고리즘마다 다를 수 있음), 재귀 호출시에 변수나, 리턴값, 위치 등이 스택메모리에 저장되게 된다. 따라서 무한 재귀가 발생하면 스택 오버플로우가 발생한다.

기저사례(base case)

재귀 함수에는 반드시 재귀의 종료 조건이 확실하게 구현되어야 한다.

종료를 위한 조건이 없다면 무한 재귀에 빠지게 되고, 결국 스택 오버플로우가 발생할 것이다.

이런 문제점을 해결하기 위해서 기저함수에 꼭 필요한 것이 재귀의 마지막을 정의하는 것이다.

재귀는 큰 문제를 동일 구조의 작은 문제로 나누어서 풀기 때문에, 재귀의 마지막에는 가장 작은 단위의 문제가 될것이다.

이렇게 가장 작은 문제를 푸는것을 기저사례(base case)라고 한다.

예를 들어

아래의 팩토리얼 재귀함수의 기저사례를 살펴보면 다음과 같다.

# 재귀를 사용한 팩토리얼 계산
def factorial_recursive(n):
    if n == 1:  # 기저 사례. n=1일 때의 팩토리얼 계산이 가장 작은 단위의 문제이다.
        return 1
    else:
        return n * factorial_recursive(n - 1)

꼬리 재귀

위에서 재귀의 문제점으로 스택 오버플로우를 꼽았다.

재귀의 과정에서 함수를 새로 호출하게 되면, 함수가 호출된 위치와 변수 등이 스택메모리에 저장되게 된다. 따라서 과하게 재귀가 많이 발생하는 경우에 스택 오버플로우가 발생하는 것이다.

이 문제를 완화하기 위한 방법이 꼬리재귀이다. 꼬리재귀는 함수의 마지막 return에서 재귀 호출을 수행하는 것이다.

코드를 이런 꼬리 재귀로 구성하게 되면 스택에 호출 주소를 저장하지 않게 된다. 따라서 이를 통해서 스택이 오버플로우 나는것을 방지할 수 있다.

덛붙여, 컴파일러의 최적화 옵션을 설정하면, 컴파일러에서 꼬리재귀 함수를 일반 반복문으로 최적화하여 오버플로우 발생을 방지할 수 있다.

재귀 VS 반복

대체로 재귀와 반복은 대체가 가능하다.

위에서 살펴본 펙토리얼을 예제로 살펴보자.

# 재귀를 사용한 팩토리얼 계산
def factorial_recursive(n):
    if n == 1: 
        return 1
    else:
        return n * factorial_recursive(n - 1)

# 재귀를 반복으로 변환한 피보나치 수열
def fibonacci_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

문제는 어떤 알고리즘을 풀이하려는지에 따라서 재귀 방식이 유용할 수도 있고, 반복이 더 효율적일 수도 있다는 것에 있다.

재귀가 효율적인 경우

문제를 작은 단위로 나누어 처리하거나, 자연스럽게 분할된 구조를 가진 경우에 유용하다.

거듭제곱 계산함수가 그 예가 될 수 있다.

def power_recursive(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        half = power_recursive(x, n // 2)
        return half * half
    else:
        return x * power_recursive(x, n - 1)

반복이 효율적인 경우

메모리 사용과 성능이 중요하게 작용하는 문제에서 유리하다.

위의 피보나치 수열의 계산이 바로 그 예이다.

def fibonacci_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

 

퀴즈

 

재귀 알고리즘에서 기저 사례(base case)의 중요성을 설명하고, 기저 사례가 없을 때 발생할 수 있는 문제를 예를 들어 설명하세요.

 

1) 재귀 알고리즘에 대한 정의

2) 기저사례의 정의

3) 기저사례의 중요성과 기저사례가 없는 경우의 문제점

 

재귀 알고리즘에서 기저 사례(base case)는 종료 조건을 의미하며, 재귀 호출이 끝날 수 있도록 설정된 기준점입니다. 기저 사례가 없다면, 함수가 무한히 자기 자신을 호출하게 되어 스택 오버플로우(Stack Overflow)가 발생할 수 있습니다.

예시: 팩토리얼 계산에서 n! = n * (n-1)!로 표현할 수 있지만, 기저 사례가 없다면 0!에 도달할 수 없습니다. 기저 사례로 0! = 1을 설정하지 않으면 함수는 계속해서 호출되면서 무한 루프에 빠지게 됩니다.

 

 

재귀 함수가 내부적으로 스택을 사용하는 이유를 설명하세요.

 

1) 재귀 함수에 대한 정의

2) 재귀 호출시의 동작

3) 스택 사용과 효과

재귀 함수는 함수 호출 시 각 호출의 상태(변수, 주소 등)를 저장해야 합니다. 이를 위해 시스템은 함수가 호출될 때마다 호출 스택(Call Stack)에 함수 정보를 저장하고, 함수가 종료되면 스택에서 해당 정보를 제거합니다. 이 구조 덕분에 재귀 함수가 중첩 호출을 할 수 있는 것입니다.

 

 

재귀 알고리즘의 기본 구조를 설명하고, 재귀와 반복(iteration) 간의 차이점을 비교하세요.

 

1) 재귀 알고리즘의 정의

2) 재귀 알고리즘의 구조

3) 반복과 재귀의 차이

재귀는 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 방법입니다. 일반적으로 재귀는 더 간결하고 직관적이지만, 반복은 메모리 사용 측면에서 효율적입니다. 재귀는 함수 호출마다 스택을 사용하기 때문에 많은 호출이 발생하면 스택 오버플로우 위험이 있지만, 반복은 일정한 메모리만 사용합니다.

예시: 피보나치 수열을 계산하는 문제에서, 재귀는 f(n) = f(n-1) + f(n-2)로 표현되지만, 반복문을 사용하면 메모리와 속도 측면에서 더 효율적인 코드로 바꿀 수 있습니다.