# 迭代、递归与Tail Call Optimization

jopen 4年前

`calc(4)=4*calc(3)  calc(3)=3*calc(2)  calc(2)=2*calc(1)  calc(1)=1*calc(0)  calc(0)=1`
</div>

`def calc(n):      """      Calculate n!        :param n: N      """      if n == 0:          return 1      if n < 0:          raise ValueError      return n * calc(n - 1)`
</div>

`calc(4)=4*calc(3)  =4*(3*calc(2))  =4*(3*(2*calc(1)))  =4*(3*(2*(1*calc(0))))  =4*(3*(2*(1*1)))  =4*(3*(2*1))  =4*(3*2)  =4*6  24`
</div>

`result=1  n=4    result=result*n=4  n=n-1=3  result=result*n=12  n=n-1=2  result=result*n=24  n=n-1=1  result=result*n=24  n=n-1=0`
</div>

`def calc(n):      """      Calculate n!      """      if n < 0:          raise ValueError      return calc_iter(n, 1)    def calc_iter(n, result):      if n == 0:          return result      return calc_iter(n - 1, result * n)`
</div>

`calc(4)=calc_iter(4, 1)  calc_iter(4, 1)  calc_iter(3, 4)  calc_iter(2, 12)  calc_iter(1, 24)  calc_iter(0, 24)`
</div>

### Tail Call Optimization (TCO)

`def calc(n):      """      Calculate n!      """      if n < 0:          raise ValueError      result = 1      while n > 0:          result, n = result * n, n - 1      return result`
</div>

### TCO的实现

Python、Java之类的非纯函数式编程语言没有实现TCO的表面原因是因为Stack trace。如果实现了TCO，那么在执行被TCO的函数期间遇到错误的时候就无法打印出Stack trace，因为这样的函数执行时不存在推入Stack的说法。

### 阅读书目

• Structure and Interpretation of Computer Program, Chapter 1
</div>