재귀함수

2020.08.03 수정

재귀(recursion) 는 반복 또는 되풀이를 의미한다.
프로그래밍에서 재귀 함수란 함수 정의 도중에 같은 이름의 함수가 나오는 경우이다.
다시말 해함수를 호출하게 되면 자기 자신을 계속 호출하게 된다.

재귀함수는 알고리즘에서 정말 많이 사용하는 기능?? 이다 .

팩토리얼

패토리얼은 어떤 수의 계승으로 1부터 어떤 수까지의 곱을 말한다.
3 의 계승은 3 x 2 x 1 을 의미하게 된다.

def factorial(n):
	return factorial(n-1) * n

if __name__ == "__main__":
	n = 3
    res = factorial(n)
    print(f"fatorial of ${n} is ${res}")

위와 같은 코드를 실행하게 되면 오류가 발생하게 된다 .

RecursionError : maximum recursion depth exceeded

오류가 발생하는 이유는 자기 자신을 계속 호출하기 때문이다.

탈출조건 이 있어야 이러한 에러가 발생하지 않는다 .

def factorial(n):
	# 탈출 조건
    if n <=1:
    	return 1
        
    return factorial(n-1) * n 

또 다른 예시를 보겠습니다.

예)
def countdown(n):
  print(n)
  countdown(n-1)

countdown(10);

countdown 함수는 받은 인자를 출력합니다.
그런데 위의 함수를 실행하면 10에서 시작해서 무한으로 마이너스 값까지 내려갑니다.

그래서 재귀함수는 아래의 절차가 꼭 필요합니다.
언제 멈출것인가?

위를 고려해 0이 되면 더이상 재귀를 이어나가지 않도록 종료 조건을 추가하겠습니다.
def countdown(n):
  print(n)

  if (n == 0):
    return None

  countdown(n-1)

countdown(10);

재귀의 이론은 위와 같이 아주 간단합니다.
재귀를 더 공부하고 싶은 분은 인터넷에 재귀 문제를 찾아 더 풀어보셔도 좋고, 알고리즘 책에서 재귀 부분만 더 읽으셔도 좋습니다.


* 문제
재귀를 사용하여 팩토리얼(factorial)을 구하는 함수를 구현해주세요.
팩토리얼이란 1에서부터 n까지의 정수를 모두 곱한것을 말합니다.

1! = 1
2! = 1 * 2
5! = 1 * 2 * 3 * 4 * 5

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


print(factorial(0))