使用前向递归删除列表元素 [英] Removing element of list with forward recursion
问题描述
我正在编写一个程序,它删除适合谓词的第一个元素,例如.
I'm writing a program which remove first element which fit to predicate eg.
remove' (fun x -> x = 2) [1;3;2;4;2] => [1;3;4;2]
问题是:如何用正向递归来写?是否可以?使用尾递归,这不是问题.如果它们不适合谓词,我只是将下一个元素添加到 acc.
and the problem is: how to write it with foward recursion? Is it possible? With tail recursion it is not a problem. I just add next elements to acc if they are not fit to predicate.
我在考虑
List.fold_right,
但也许有不同的方法来做到这一点?
but maybe is there different way to do this?
推荐答案
没有前向递归"这样的东西.尾递归定义了一种特殊的递归,它发生在尾位置.当你想引用一个不在尾位置的递归时,你称之为非尾递归"
There is no such thing as "forward recursion". Tail recursion defines a special kind of recursion, that occurs in a tail position. When you want to refer to a recursion that is not in a tail position, you call it "non tail recursive"
在您指定的代码中,根本没有递归.因此,我建议您首先尝试编写 remove_if
函数并尝试弄清楚它是尾部还是非尾部.
In the code you've specified there is no recursion at all. So, I would suggest you first of all to try to write remove_if
function and try to figure out whether it is tail or non-tail.
我通常会尽量不为别人解决家庭作业,但在这种情况下,我将通过为您提供remove_if
函数的最常见定义来给你一个小启动:
I usually try no to solve homework for others, but at this case I will give a little kick start, by providing you with the most common definition of remove_if
function:
let rec remove matches = function
| [] -> []
| x :: xs when matches x -> remove matches xs
| x :: xs -> x :: remove matches xs
此函数中出现了两次递归:
There are two occurrences of recursion in this function:
| x :: xs when matches x -> remove matches xs
^^^^^^^^^^^^^^^^^
last expression -
tail recursion
| x :: xs -> x :: remove matches xs
^^^^^^^^^^^^^^^^^
not the last -
non tail recursive
所以,最后一种情况需要澄清:在 x
可以添加到 remove 匹配 xs
的结果之前,需要评估后一个表达式.这意味着计算机需要将 x
存储在某处,以等待 remove matching xs
被评估.
So, last case needs some clarification: before the x
can be prepended to the result of remove matches xs
the latter expression needs to be evaluated. That means that computer needs to store x
somewhere, to wait until remove matches xs
is evaluatd.
所以,没有有趣的部分,你有一个非尾递归版本.现在,尝试以尾部递归方式实现它.玩得开心
!
So, no the fun part, you have a non-tail recursive version. Now, try to implement it tail recursively. Have fun
!
这篇关于使用前向递归删除列表元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!