[1주차] 재귀함수의 장단점 (+stack overflow/ 재귀 한계)

 

재귀함수의 장단점
장점
1) 코드가 더 깔끔하고 이해하기 쉽다.
2) 반복문을 사용하지 않고 복잡한 문제를 해결할 수 있다.
단점
1) 함수 호출시 메모리가 추가적으로 사용돼 메모리 소비가 많으며, 잘못하면 스택 오버플로우를 일으킬 수 있다.
2) 반복문에 비해 빈번한 메모리 할당/해제로 실행 속도가 느릴 수 있다.

 

재귀함수란?

정의)

- 재귀(Recursion) 자기 자신을 재참조하는 방법

- 재귀함수 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식

따라서, 특정 분기(종료 조건 만나기 전)까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용

- for, while문 등의 반복문으로 구현가능한 로직 모두 재귀함수로 구현 가능

내가 생각하는 재귀에서의 중요 포인트
1) 예외 케이스
2) 재귀의 종료 조건
(이 둘은 결합되서 사용..!)

(----아직 정확하지 않아서 수정해 봐야할 부분---)

1) 예외 케이스

1-1) if 로 빼기

1-2) try/ except로 빼기

try로 실행하다가, 예외인 상황을 만나면 except로 빼기.

 

2) 재귀 종료 조건

예외 케이스와 결합되어 재귀를 빠져나감. 

(-------------------------------------------)

 

대표적 예시)

팩토리얼 함수

def factorial(n):
	if n == 1:
    	return 1	# 예외조건과 종료조건
    return n * factorial(n - 1)

 

 

메모리 관점)

출처: https://catsbi.oopy.io/dbcc8c79-4600-4655-b2e2-b76eb7309e60

매커니즘)

위의 그림은 factorial(5)를 부를 때, 쌓이는 콜스택을 그림으로 표현한 것이다.

함수 호출할 때마다, 매개변수, 지역변수, 반환주소값등을 모두 저장하게 되는데,

1) factorial(5)를 호출하게 되면, factorial(5)의 지역변수/ 반환주소 값/ 매개변수 가 쌓이게 됨.

2) 반환값인  5 * factorial(5 - 1)를 통해 factorial(4)가 호출되고 반환을 기다리게 됨.

3) factorial(4)를 호출하게 되면, factorial(4)의 지역변수/ 반환주소 값/매개변수 가 쌓임.

4) 반환 값인 4 * factorial(4 - 1)을 통해 factorial(3)이 호출되고 반환을 기다리게 됨.

....

11) factorial(1)을 호출하게 되면, if(n ==1)의 종료조건에 의해, 재귀를 빠져나오게 됨.

이렇게 순차적으로 콜스택이 쌓이게 된다.

콜스택에 LIFO(Last Input First Out)형태로 차례대로 꺼내지게 된다.

 

주의할 점)

스택오버플로우

 

스택오버플로우(Stackoverflow)

정의)

스택에 무한대로 쌓이면서, 스택 오버플로우가 발생하게 된다. 

 

발생 예시)

def factorial(n):
	return n * factorial(n - 1)	# 종료 조건이 없으므로, 무한대로 재귀가 돈다.

 

이렇게 가능한 스택이 없다는.. 오류를 마주할 수 있게 된다..!

 

원인)

종료조건에 제대로 안걸리게 되면, stackoverflow가 발생하게 된다.

왜냐믄, 컴퓨터 메모리에 한계가 있으니깐..! 

 

문제 해결 방법) 

우선, 재귀 횟수 한계를 확인해보자!

 

재귀 횟수 한계 확인)

파이썬의 재귀 한계횟수는 다음 명령어를 통해 1000임을 확인할 수 있다.

import sys
print(sys.getrecursionlimit()) # 출력 값 1000

이를 변경해보자..!

 

재귀 횟수 한계 변경 방법)

재귀 한계 횟수를 변경하고 싶다면, 다음 명령어를 통해 10000으로 늘릴 수 있다.

import sys
sys.setrecursionlimit(10000)
print(sys.getrecursionlimit())  # 출력값 10000

 

단, 표준 한계치가 설정되어 있기에 이를 이용하는 것은 위험하다..!

Python은 함수형 언어가 아니고, 꼬리 재귀는 특별히 효율적인 기술이 아니다.

가능하다면, 알고리즘을 반복적으로 이용하는 것이 더 좋은 아이디어이다!

 

 

참조)

https://catsbi.oopy.io/dbcc8c79-4600-4655-b2e2-b76eb7309e60

재귀함수의 장점과 단점 그리고 해결책

https://velog.io/@jsin2475/Python%EC%97%90%EC%84%9C-%EC%B5%9C%EB%8C%80-%EC%9E%AC%EA%B7%80-%ED%9A%9F%EC%88%98%EB%8A%94-%EB%AA%87-%EB%B2%88%EC%9D%B4%EA%B3%A0-%EC%96%B4%EB%96%BB%EA%B2%8C-%EC%A6%9D%EA%B0%80%EC%8B%9C%ED%82%AC%EC%88%98-%EC%9E%88%EB%82%98%EC%9A%94

Python에서 최대 재귀 횟수는 몇 번이고 어떻게 증가시킬수 있나요??