[자료구조] 재귀함수

재귀함수란 무엇일까

컴퓨터 과학에 있어서 재귀(Recursion)은 자신을 정의할 때 자가 자신을 재 참조하는 방법을 의미한다.
주로 재귀 호출의 형태로 많이 사용되며, 반드시 종료 조건이 포함되어야 한다. (무한 루프를 방지 하기 위함)

 

반복문을 사용하는 코드는 항상 재귀함수를 통해 구현하는 것이 가능하며, 그 반대도 가능하다.

 

이전에 살펴본 알고리즘 중 DFS 역시 재귀 형식으로 구현이 가능하다.

 

이외에도 대표적인 예제를 살펴보고자 한다.

---

재귀함수의 대표적인 예 - 팩토리얼

n!의 형태로 표현되는 팩토리얼은 풀어서 작성하면 다음과 같다.

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

 

이걸 재귀함수를 이용한 코드(파이썬)을 작성하면 다음과 같다.

def fact(n):
    if n==1:
        return 1
    else:
        return n * fact(n-1)

 

만일 n이 3라면 다음과 같이 되는 것이다.

fact(3) -> return 3 * fact (2) -> return 3 * 2 * fact(1) -> return 3 * 2 * 1     =>     6

 

위의 코드에서도 앞서 말한 주요 포인트인 종료조건이 명시되어 있다.

if n == 1:
    return 1

이 부분이다.

 

재귀는 본인을 재 호출하는 개념이라 이해 자체는 어렵지 않으나,
코드가 복잡해질 수록 스택 오버플로우를 주의해야 한다.

이 부분만 유의하면 굉장히 유용한 알고리즘 중에 하나 이다.

 

---

예제 문제로는 다음과 같은 문제들이 있다.

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

10829번: 이진수 변환

https://programmers.co.kr/learn/courses/30/lessons/60058

코딩테스트 연습 - 괄호 변환