python 함수 재 귀 꼬리 재 귀

참고:
http://www.liaoxuefeng.com/wiki/001374738125095c955c1e6d8bb493182103fac9270762a000/00137473836826348026db722d9435483fa38c137b7e685000  
#############################################
함수 내부 에서 다른 함 수 를 호출 할 수 있 습 니 다.만약 한 함수 가 내부 에서 자신 을 호출 한다 면, 이 함 수 는 재 귀 함수 이다.
단계 곱 하기:

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

재 귀 함수 장점: 정의 가 간단 하고 논리 가 뚜렷 하 다.이론 적 으로 모든 재 귀 함 수 는 순환 방식 으로 쓸 수 있 지만 순환 의 논 리 는 재 귀 가 뚜렷 하지 않다.
재 귀 함 수 를 사용 하려 면 스 택 이 넘 치지 않도록 주의해 야 합 니 다.컴퓨터 에서 함수 호출 은 스 택 (stack) 이라는 데이터 구 조 를 통 해 이 루어 집 니 다. 한 함수 호출 에 들 어 갈 때마다 스 택 프레임 을 추가 하고 함수 가 돌아 올 때마다 스 택 프레임 을 한 층 줄 입 니 다.스 택 의 크기 가 무한 한 것 이 아니 기 때문에 재 귀적 호출 횟수 가 너무 많 으 면 스 택 이 넘 칠 수 있 습 니 다.

fact(1000)

#################################################
재 귀 호출 스 택 넘 치 는 방법 을 해결 하 는 것 은 꼬리 재 귀 를 통 해 최적화 하 는 것 이다. 사실상 꼬리 재 귀 와 순환 의 효 과 는 같 기 때문에 순환 을 특수 한 꼬리 재 귀 함수 로 보 는 것 도 가능 하 다.
끝 재 귀: 함수 가 돌아 올 때 자신 을 호출 하고 return 문 구 는 표현 식 을 포함 할 수 없습니다.이렇게 하면 컴 파일 러 나 해석 기 는 꼬리 재 귀 를 최적화 시 켜 재 귀 자 체 를 몇 번 호출 하 든 하나의 스 택 프레임 만 차지 하고 스 택 이 넘 치 는 상황 이 발생 하지 않도록 할 수 있다.
상기 코드 에서 fact 함 수 는 return n * fact (n - 1) 가 곱셈 표현 식 을 도 입 했 기 때문에 끝 재 귀 가 아 닙 니 다.코드 수정:

def fact(n):
      return fact_iter(n, 1)

def fact_iter(num, product):
      if num==1:
         return product
      return fact_iter(num-1, num*product)

return 문 구 는 재 귀 함수 자체 만 되 돌려 줍 니 다. num - 1 과 num * product 는 함수 호출 전에 계산 되 고 함수 호출 에 영향 을 주지 않 습 니 다.
################################################################
재 귀적 호출 시 최 적 화 를 하면 스 택 이 증가 하지 않 기 때문에 아무리 호출 해도 스 택 이 넘 치지 않 습 니 다.
Python 해석 기 가 최적화 되 지 않 았 기 때문에 끝 재 귀 방식 을 사용 하면 스 택 이 넘 칠 수 있 습 니 다.
재 귀 함수 장점: 논리 가 뚜렷 하고 간단 하 다.단점: 너무 깊 은 호출 로 인해 스 택 이 넘 칩 니 다.
끝 재 귀 에 최 적 화 된 언어 는 끝 재 귀 를 통 해 스 택 이 넘 치 는 것 을 방지 할 수 있다.꼬리 재 귀 는 사실상 순환 등가 이 고 순환 문 이 없 는 프로 그래 밍 언어 는 꼬리 재 귀 를 통 해 순환 할 수 밖 에 없다.
Python 표준 해석 기 는 끝 재 귀 를 최적화 하지 않 았 고 모든 재 귀 함수 에 스 택 넘 치 는 문제 가 존재 합 니 다.