코딩테스트 - 재귀함수

사실 재귀함수에 대해서는 코딩테스트 대비 - DFS / BFS에서 살짝 다룬 적이 있다. 하지만 재귀함수만 따로 코드로 구현하지는 않았기에 이번 글에서 다시 설명하고 코드로 구현하고 설명해보려 한다.

재귀함수는 반복적인 것을 해결할 때 좋은 방식이다. '재귀적이다'라는 말은 어떤 사건이 자신을 포함하고 자기 자신을 사용하여 정의될 때 사용한다고 한다. 즉, 재귀함수는 함수의 정의단계에서 자신을 재참조하는 함수를 말한다. 재귀함수는 자신의 로직을 함수 내부에서 반복하다가 일정 조건(종료 조건)이 만족되면 함수를 이탈하는 것이다. 따라서, 종료조건을 제대로 설정하지 않으면 무한히 반복하게 된다. 사실 나는 종료 조건을 설정하는 것이 까다롭다고 생각하기 때문에 재귀함수를 선호하지는 않았다. 실제로 임베디드 펌웨어를 만들거나 졸업작품을 하면서 거의 사용하지 않았다. 하지만 코딩테스트에서는 재귀함수를 이용하면 시간이 단축되는 경우도 있고 간결한 프로그래밍이 가능하다.

1. Code
   재귀함수의 예제는 두가지를 하려고 한다. 첫번째는 팩토리얼, 두번째는 이진법변환이다.

num = 5


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


def to_odd(n=num):
    if n < 2:
        return str(n)

    if n % 2 == 0:
        return to_odd(n//2) + '0'
    else:
        return to_odd(n//2) + '1'


print(f"{num}의 factorial은", factorial())
print(f"{num}의 이진수는", to_odd())

출력

5의 factorial은 120
5의 이진수는 101