재귀함수

자기 자신을 다시 호출하는 함수

재귀함수 장단점

장점	단점
1. 코드가 간결해진다.	메모리를 많이 차지한다.
2. 루프문을 사용하지 않아도 된다.

재귀의 한계

함수가 자신을 호출할 때마다 중간 값을 저장하기 위한 메모리가 필요하다. 따라서 재귀함수는 일반적인 비재귀함수보다 훨씬 많은 메모리를 소비한다. 파이썬은 재귀 호출 제한을 '3000'으로 설정한다.

간단한 예를 들자면, 이렇게 할 경우에는

def example():
    print('hello')
    example()

example()

무한히 실행될 것 같지만 RecursionError가 난다. 내용을 보면 파이썬 객체를 호출할 수 있는 최대 반복 깊이를 초과했다고 나온다. 파이썬에는 재귀함수를 이용하여 반복할 수 있는 횟수가 '3000'으로 한정되어 있기 때문이다. 이 때 제한되어 있는 함수를 왜 사용하냐 생각할 수 있지만, 재귀함수는 적절한 순간에 종료시키도록 구현되어 있지 않은 경우를 대비하여 반복횟수에 제약이 걸려있지만, 원하는 답을 얻기에 충분한 반복횟수를 가지고 있다. 아래는 탈출조건이 존재하지 않으니 무한루프로 계속해서 'hello'를 출력하고 있다. 때문에 탈출조건을 걸어주어야한다.

hello
hello
...
hello
Traceback (most recent call last):
  File "pro.py", line 5, in <module>
    exam()
  File "pro.py", line 3, in exam
    exam()
  File "pro.py", line 3, in exam
    exam()
  File "pro.py", line 3, in exam
    exam()
  [Previous line repeated 992 more times]
  File "pro.py", line 2, in exam
    print('hello')
RecursionError: maximum recursion depth exceeded while calling a Python object

return의 의미는 반환을 하는 의미도 있지만 함수를 종료한다는 뜻도 가지고 있다.
재귀함수도 반복문처럼 return을 써서 무한루프를 탈출할 수 있다.

def exam(i):
    print(f'hello {i}')
    i -= 1
    if i == 0:
        return None
    else:
        exam(i)

exam(10)

아래와 같이 출력되고 해당 함수는 종료된다.

hello 10
hello 9
hello 8
hello 7
hello 6
hello 5
hello 4
hello 3
hello 2
hello 1

재귀 제한 삭제

재귀 제한을 필요한 재귀보다 큰 수로 설정하여 재귀 제한을 해결할 수 있다.

import sys
sys.setrecursionlimit(5000)

---

재귀함수를 작성할 때에는 함수 내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료 조건이 꼭 포함되어야한다는 부분을 인지하고 작성하면 무한 루프를 방지할 수 있다.

---

예

예1. 구구단 출력

def multiplication(n,i):
    if i == 10:
        print('End')
    else:
        print(f'{n} x {i} = {n*i}')
        multiplication(n, i+1)

multiplication(2, 1)

예2. 팩토리얼

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

print(factorial(5))