python 两种递归方法求1,1,1,3,5,9,17,31…
时间: 2024-03-23 15:42:35 浏览: 13
这个数列是前三项是1,后面每一项都是前三项的和。下面是两种递归方法求这个数列的第n项。
方法一:直接递归
直接递归求解,在代码中调用自身函数,直到找到终止条件。
```python
def recursion(n):
if n == 1 or n == 2 or n == 3:
return 1
else:
return recursion(n-1) + recursion(n-2) + recursion(n-3)
```
方法二:尾递归
尾递归是指递归函数在最后一步调用自身,不需要进行额外的计算。尾递归可以优化递归算法的性能,因为它可以避免递归过深导致的栈溢出问题。
```python
def tail_recursion(n, a=1, b=1, c=1):
if n == 1 or n == 2 or n == 3:
return 1
elif n == 4:
return 3
elif n == 5:
return 5
elif n == 6:
return 9
elif n == 7:
return 17
else:
return tail_recursion(n-1, b, c, a+b+c)
```
其中,a、b、c分别是数列中的三个前缀项。在每次函数调用时,将b、c、a+b+c作为新的前缀项传入下一次递归。这样,每次函数调用都只需要计算新的前缀项,避免了递归过深导致的栈溢出问题。