[알고리즘 자습]재귀(recursive) 함수 - N까지의 합, 거듭제곱, 구구단, 팩토리얼 등 예제- Python3

알고리즘을 공부하는 사람은 누구나 한번쯤 재귀함수에 대해 들어봤을 것이다. 그러나, 재귀적인(recursive) 방법은 코드가 직관적이긴 하나, 디버깅이 힘들고, 그 아이디어를 짜는 것이 생각보다 힘들다보니 보통은 반복적인(iterative) 방법으로 코드를 작성한다. 그리고 속도도 일반적으로 재귀보다는 반복이 빠르다고 하니, 굳이 재귀를 써야 하나 싶다. 그러나, 재귀를 사용할 경우 반복으로 해결할 때 문제가 너무 복잡해지는 것을 예방할 수 있다. 그런 측면에서, 코딩 테스트 준비생들에게는 꼭 알아야 할 방법이라 할 수 있다. 

재귀함수란?

재귀함수란, 어떤 함수 func(n)이 있다고 할 때, 이 함수의 내부에서 자기 자신을 호출하는 함수를 말한다. 보통의 재귀함수의 구성은 다음과 같다. 

def sol(n):
    if n == 5:
        return 

    else:
    	print("자기자신 호출")
        return sol(n+1)

sol(0)

 위 코드는 재귀함수의 동작에 대해 알아보기 위해 임의로 쓴 코드이다. 위 코드를 예로 들어서 재귀 함수의 생김새를 알아보자. 

재귀 함수는

1.  자기 자신을 호출하는 부분
2.  일정 조건을 만족하면 호출을 정지하고 어떤 값을 return하는 부분

이 두 분으로 나뉘어진다. 그리고 함수 호출은 메모리의 스택 영역에 쌓이게 되는데, 스택은 후입선출(LIFO)방식으로 데이터를 저장하는 자료구조임을 우리는 알고 있다. 따라서, 위 함수를 실행했을 때 스택영역에 쌓이는 함수는 아래와 같다.

이렇게, 재귀 함수를 구성하는 요소와 흐름에 대해 알아보았다. 그럼, 재귀함수를 짜는 법을 알아보자

1.  자신을 호출하는 것을 정지시키는 조건을 만들어야 한다. 

위의 경우에서는, n이 5가 되면 정지하고 return을 한다. 그러면, 그전에 호출된 함수(sol(4))에서 그 return값을 받아서, sol(3)의 결과를 만들수 있게 한다. 어느 순간 정지하는 조건을 만들지 않으면, 메모리에 함수가 무한히 쌓여서 스택 오버플로우 현상이 발생한다. 

2. 한 동작마다 해야하는 것들을 정의해서, 함수 내부

에 써넣는다. 

위의 경우에서는 print문에 해당한다. 재귀라는것 또한 어떤 행동을 반복한다는 것인데, 그 반복에 해당하는 동작을 써넣는다. 

3. 다음 함수를 호출할 때, 파라미터로 어떤 것들을 넘겨줘야 할 지 정해야 한다. 

이는 생각보다 좀 어려운데, 매 동작마다 필요한 데이터를 넘겨줘야 한다. 그리고 계속 업데이트하면서 사용할 변수가 있는 경우는 전역변수를 쓰기도 해야 한다. 이런 저런 경우가 있으므로, 문제를 잘 읽고 판단하도록 하자. 

여기까지, 재귀함수가 무엇인지, 어떻게 구성되어 있는지, 어떻게 흘러가는지, 어떻게 만들어야 할지 간략히 알아봤다. 이를 예제를 통해 실습해보자.  아래 예제들은, 충~~~분히 반복문으로 풀 수 있지만, DFS 등의 좀더 고차원적인 문제의 기본이 되는 재귀함수의 연습을 위해 실습하는 것이므로, 꼭 재귀로 풀길 바란다. 

예제1: N까지의 합

n이 주어졌을 때, 0부터 n까지의 수들을 더한 값을 출력하라

def solution(n):
    if n == 0:
        return 0
    else:
        return n + solution(n-1)

 

일단, 입력받은 n이 0이라면 호출을 멈춘다. 그렇지 않다면, n + solution(n-1)을 호출한다. 이 문제 또한 메모리 스택을 보면서 풀어보자. 

이렇게 답을 출력함을 알 수 있다. 재귀함수가 어떻게 흘러가는지 보려면, 이렇게 메모리 스택을 그려보는게 나는 제일 좋더라.

 

예제2: 거듭제곱

def solution2(x, n):
    if n == 0:
        return x
    else:
        return x * solution2(x, n-1)

거듭제곱을 구현한 코드이다. x의 (n - 1)승을 구하는 코드이다. 메모리 스택을 통해 결과를 보자면 다음과 같다.

 

예제3: 구구단

이 예제부터는, 코드만 올려놓겠다. 

def solution(n, count):
    if count == 9:
        print(n, "*", count, "=", n*count)
        return
    else:
        print(n, "*", count, "=", n*count)
        return solution(n, count+1)

 

예제4: 베열의 합

def solution2(arr, i):
    if i == len(arr)-1:
        return arr[i]
    else:
        return arr[i] + solution2(arr, i+1)

 

예제5: 순차 탐색

def solution(arr, target, n):
    if arr[n] == target:

        return n
    else:
        return solution(arr, target, n+1)


arr = [1, 6, 10, 5, 2, 7]
target = 7

 

예제6: 유클리드 호제법

def solution(m, n):
    if m < n:
        m, n = n, m
    if m % n == 0:
        return n
    else:
        print(m, n)
        print(n, m % n)
        return solution(n, m%n)

 

예제7: 이진수 변환

def solution(n, answer):
    if n >= 2:
        print(n % 2)
        answer.append(n%2)
        return solution(int(n/2), answer)
    else:
        print(n)
        answer.append(n)
        return

answer = []
n = 10
solution(n, answer)
string = ""
for i in range(len(answer)):
    j = len(answer) - i - 1
    string += str(answer[j])

print(string)

예제8: 팩토리얼

def solution(n):
    print(n)
    if n == 1:
        return 1
    else:
        print("Return, ", n)
        return n * solution(n-1)
n = 5
print(solution(n))

 

 

이렇게, 재귀함수를 이용해서 간단한 문제들을 풀어보고 정리했다. 이렇게 쉬운 문제 풀어서 뭐하겠냐고 생각할 지도 모르겠는데, DP공부하면서 기본적인 예제 많이 풀었던게 어려운 문제 푸는데 도움이 많이 되었다. 이제 기본적인 재귀함수를 알아봤으니, DFS/BFS문제도 풀어보도록 하겠다.