재귀 개념 (Factorial, Fibonacci Number)

재귀란?

컴퓨터 과학에서 재귀의 사전적 정의는 다음과 같다.

재귀(Recursion) : 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다.

이를 프로그래밍에 적용하여 재귀 호출(Recursive call)의 형태로 많이 사용한다.

 

재귀 호출(Recursive call)

개념

• 재귀적인 루틴에서는 자기 자신을 호출하여 하위 작업을 처리하는 방식으로 작업의 일부분을 수행한다.
• 재귀 호출을 하다보면 자신을 호출하지 않고도 처리할 수 있는 하위 작업이 나오는데 이를 기본 케이스(base case)라 부르고, 루틴에서 자신을 호출하여 하위 작업을 수행하는 케이스는 재귀 케이스(recursive case) 라고 부른다.
• 모든 재귀적인 케이스는 결국에는 기본 케이스(종료조건)으로 넘어가야만 한다.

특징

• 재귀 호출이 가독성을 높이고 구현을 간결하게 하는 장점이 있지만, 반복되는 호출에 따르는 오버헤드로 오히려 효율이 떨어진다.
• 모든 재귀 함수는 반복문으로 변환이 가능하기 때문에 복잡도가 크게 차이나지 않는다면 반복문을 사용하는 것이 더 효율적이다.

 

예1) Factorial

간단하고 널리 알려져 있는 예제인 팩토리얼(factorial)연산으로 재귀 호출 개념을 이해해보자.

음이 아닌 정수 n의 팩토리얼(n!)은 1부터 n까지의 모든 정수를 곱한 값이다.
예를 들어 3! = 3 * 2 * 1 = 6 과 같이 나타낼 수 있다.

팩토리얼을 다음과 같이 형식적으로 정의할 수 있다.

1. 0! = 1! = 1
2. n! = n * (n-1)!

이 정의로부터 재귀적으로 구현하는 방법을 유추해보자면, 10의 팩토리얼인 10! 은 10 x 9! 로 구할 수 있고, 9! 은 9 x 8! 로 구할 수 있다.

 

다음은 팩토리얼을 재귀적으로 구현한 함수이다.

def factorial(n):
    if n == 0: # 기본 케이스
        return 1    
    return n * factorial(n-1) # 재귀 케이스

x = factorial(3) # x = 6

• 재귀 호출을 반복할 때마다 n의 값이 1씩 줄어들면서 결국에는 기본 케이스에 다다를 것이다.
• 만약 기본 케이스에 이르도록 만들지 못한다면 재귀 호출을 무한히 반복하게 된다.
  • 이 경우 언젠가 스택 오버플로가 발생하면서 프로그램이 멈춰버리게 된다.
• 따라서 모든 재귀적인 케이스는 결국에는 기본 케이스(종료조건)으로 넘어가야만 한다.

 

factorial 함수를 반복문으로 구현하면 다음과 같다.

def factorial(n):
    val = 1
    for i in range(1, n+1):
        val *= i
    return val

x = factorial(3) # x = 6

 

예2) Fibonacci Number

피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤에 모든 항은 바로 앞 두 항의 합인 수열이다.

1, 1, 2, 3, 5, 8, 13, ...

피보나치 수(Fn)를 점화식으로 나타내면 다음과 같다.

 

피보니치 수열을 재귀적으로 구현한 함수이다.

def fibonacci(n):
    if n <= 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

x = fibonacci(3) # x = 2

 

반복문으로 구현했을 때 다음과 같다.

def fibonacci(n):
    a, b = 1, 1

    if n <= 2:
        return 1

    for i in range(1, n):
        a, b = b, a+b

    return a

x = fibonacci(3) # x = 2