如何从递归和尾递归列表中获取最后两个值? [英] How to get the 2 last values from a list in recursion and in tail-recursion?
问题描述
我需要一个谓词last_two(LST,Y,Z)
将列表的最后一个值分配给 Z倒数第二个到 Y.我怎样才能在递归中做到这一点?我怎么能在尾递归中做到这一点?谢谢!
I need a predicate last_two(LST,Y,Z)
that assigns the last value of a list to Z
and the second-to-last to Y.
How can I do it in recursion? and how can I do it in tail-recursion?
thanks!
这是一个带有尾递归的代码,我可以让它更高效吗?
Here is a code with tail recursion, can I make it more efficient?
last2_2([_|[H1|[H2|T]]],Y,Z):-last2_2([H1|[H2|T]],Y,Z).
last2_2([H1,H2],H1,H2).
推荐答案
你可以简化递归的情况:
You could simplify the recursive case:
last2_2([_|T],X,Y) :- last2_2(T,X,Y).
这将使每个递归案例更快(更少的模式匹配),但会导致它走得太远,并且必须回溯以获取最后两个元素.随着列表变长,这可能会更有好处(因为回溯的数量与列表的长度无关).
This would make each recursive case faster (less pattern-matching), but causes it to go too far, and have to backtrack to get the last 2 elements. This would probably be of more benefit as the list gets longer (as the amount of backtracking is independent of the length of the list).
您可以更进一步,将递归情况替换为:
You could take this a step further, replacing the recursive case with:
last2_2([_,_|T],Y,Z):-last2_2(T,Y,Z).
last2_2([_,A,B],A,B).
在这里,递归案例一次剥离 2 个元素(以更多的模式匹配为代价),我们需要第二个基本案例来处理奇数长度的列表.
Here, the recursive case strips off 2 elements at a time (at the cost of some more pattern-matching), and we need a second base case to handle odd-length lists.
这篇关于如何从递归和尾递归列表中获取最后两个值?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!