递归 [英] recursion
问题描述
有人可以解释一下
>> def f（l）：
如果l == []：
返回[]
否则：
返回f（l [1：]）+ l [：1]＃< =不能算这个，最后总结怎么样？
谢谢！
Gigs_写道：
有人可以解释我这个
def f（l）：
如果l == []：
返回[]
else：
返回f（l [1：]）+ l [：1]＃< =不能算这个，怎么是
最后总和？
如果你考虑从最简单的情况构建：
f（[]）= []
f （[''a'']）= f（[]）+ [''a''] = [] + [''a''] = [''a'']
现在f（[''''，''b'']）将是：
f（[''b'']）+ [''a''' ]
= [''b''] + [''a'']
= [''b''，''a'']
同样，对于f（[''a''，''b''，''c'']），这将是：
f（[' 'b''，''c'']）+ [''a'']
当然，如果你想这样做，你总是可以使用list.reverse（）但是我猜你试图处理递归而不是仅仅反转一个
列表。我发现从基础案例中思考有助于在尝试理解递归代码时，但在编写代码时，我倾向于以另一种方式工作
。
-
我在CAMbridge，而不是SPAMbridge
在2007-09-13，Gigs_< gi ** @ hi.t-com.hrwrote：
有人能解释一下这个
> def f（l）：
如果l == []：
return []
else：
返回f（l [1：]）+ l [：1]＃< =不能算这个，所有的总和怎么样？
用简单的英语，上面的程序说：
如果列表中列表l中的项目总和为零是空的。
否则，总和是第一项的价值加上列表中其余项目的总和
.
好吧，如果它不是有点儿马车就会说。 l [：1]
并不是一个数字，而是一个包含一个
数的列表，所以上面的程序不是你说的那样确实如此。
它应该是这样的：
def my_sum（seq）：
if len（ seq）== 0：
返回0
否则：
返回seq [0] + my_sum（seq [1：]）
递归的艰难部分是需要信念的飞跃，而b $ b b相信它是有效的。但是，你经常可以使用归纳证明正确性证明来帮助消除信仰。
证明my_sum（seq）计算中的项目总和seq（这个
证明模仿Max Hailperin，Barbara
Kaiser和Karl Knight在_Concrete Abstractions_中写的证明）：
基本情况：由于if，len和==的评估规则，当len（seq）为
时，my_sum（seq）以值0终止。
归纳假设：假设my_sum（subseq）评估为seq的子序列中所有项目的总和为
，其中0 <=
len（ subseq）< len（seq）。
归纳步骤：考虑评估my_sum（seq），其中seq的
长度大于0.如果
my_sum（seq [1：]）终止，并且将具有seq [0] +
my_sum（seq [1：]）的值。因为seq [1：]计算为
的后续序列seq中的其余项目（除第一个之外的所有项目），0< =
len（subseq） < len（seq），我们可以假设my_sum（seq [1：]）确实终止了我们的归纳
假设，其值为
等于其余的项目在seq。
因此，seq [0] + my_sum（seq [1：]）评估为seq [0] +
之和的全部seq [1：]中的项目。因为seq [0] +
的总和，seq中其余项目的总和等于
seq中所有项目的总和，我们看到my_sum（seq）确实在seq的子序列正确操作的归纳
假设下，以任意长度的seq终止正确的
值。
结论：因此，通过对seq的长度
的数学归纳，my_sum（seq）以所有
的总和的值终止seq中的项目seq的长度
但我真的更喜欢第一个简单的英文版本。 ;）
-
Neil Cerutti
对于那些有孩子并且不知道的人，我们在楼下有一个托儿所
。 --Church Bulletin Blooper
Neil Cerutti写道：
2007-09-13，Gigs_< gi**@hi.t-com.hrwrote：
>有人可以解释一下这个
>>>> def f（l）：
如果l == []：
返回[]
否则：
return f（l [1：]）+ l [：1]＃< =不能算这个，所有的总结怎么样？
用简单的英文，上面的程序说：
如果列表中列表l中的项目总和为零是空的。
否则，总和是第一项的值加上列表中其余项目的总和
。
我错过了什么吗？这与求和有什么关系？
>> def f（l） ：
...如果l == []：
... return []
...其他：
...返回f（l [1：]）+ l [：1]
...
>> f（[1,2,3,4]）
[4,3,2,1]
Ian
Can someone explain me this
>>def f(l):
if l == []:
return []
else:
return f(l[1:]) + l[:1] # <= cant figure this, how is all sum at the end?
thanks!
Gigs_ wrote:Can someone explain me this
def f(l):
if l == []:
return []
else:
return f(l[1:]) + l[:1] # <= cant figure this, how is
all sum at the end?If you think about building up from the simplest case:
f([]) = []
f([''a'']) = f([]) + [''a''] = [] + [''a''] = [''a'']
Now f([''a'', ''b'']) is going to be:
f([''b'']) + [''a'']
= [''b''] + [''a'']
= [''b'', ''a'']
Similarly, for f([''a'', ''b'', ''c'']), that will be:
f([''b'', ''c'']) + [''a'']
Of course, if you want to do this you can always use list.reverse() but I
guess you''re trying to get a handle on recursion rather than just reverse a
list. I find thinking up from the base case helps when trying to
understand recursive code but when writing it, I tend to work the other way
around.
--
I''m at CAMbridge, not SPAMbridge
On 2007-09-13, Gigs_ <gi**@hi.t-com.hrwrote:Can someone explain me this
>def f(l):
if l == []:
return []
else:
return f(l[1:]) + l[:1] # <= cant figure this, how is all sum at the end?In plain English, the above program says:
The sum of the items in list l is zero if the list is empty.
Otherwise, the sum is the value of the first item plus the sum of
the rest of the items in the list.
Well, it would say that if it weren''t somewhat buggy. l[:1]
doesn''t evaluate to a number, but to a list containing one
number, so the above program doesn''t do what you say it does.
It should read something like:
def my_sum(seq):
if len(seq) == 0:
return 0
else:
return seq[0] + my_sum(seq[1:])
The tough part of recursion is the leap of faith required to
believe that it works. However, you can often use an inductive
proof of correctness to help obviate the faith.
Proof that my_sum(seq) computes the sum of the items in seq (this
proof is modeled on proofs written by Max Hailperin, Barbara
Kaiser, and Karl Knight, in _Concrete Abstractions_):
Base case: my_sum(seq) terminates with value 0 when len(seq) is
zero, because of the evaluation rules for if, len and ==.
Induction hypothesis: Assume that my_sum(subseq) evaluates to
the sum of all the items in subsequence of seq, where 0 <=
len(subseq) < len(seq).
Inductive step: Consider evaluating my_sum(seq) where the
length of seq is greater than 0. This will terminate if
my_sum(seq[1:]) terminates, and will have the value of seq[0] +
my_sum(seq[1:]). Because seq[1:] evaluates to the subsequence of
the rest of the items in seq (all except the first), and 0 <=
len(subseq) < len(seq), we can assume by our induction
hypothesis that my_sum(seq[1:]) does terminate, with a value
equal to the sum of the the rest of the items in seq.
Therefore, seq[0] + my_sum(seq[1:]) evaluates to seq[0] + the
sum of all the items in seq[1:]. Because seq[0] + the sum of
the rest of the items in seq equals the sum of all the items in
seq, we see that my_sum(seq) does terminate with the correct
value for any arbitrary length of seq, under the inductive
hypothesis of correct operation for subsequences of seq.
Conclusion: Therefore, by mathematical induction on the length
of seq, my_sum(seq) terminates with the value of the sum of all
the items in seq for any length of seq.
But really I prefer the first first plain English version. ;)
--
Neil Cerutti
For those of you who have children and don''t know it, we have a nursery
downstairs. --Church Bulletin Blooper
Neil Cerutti wrote:On 2007-09-13, Gigs_ <gi**@hi.t-com.hrwrote:>Can someone explain me this
>>>>def f(l):if l == []:
return []
else:
return f(l[1:]) + l[:1] # <= cant figure this, how is all sum at the end?
In plain English, the above program says:
The sum of the items in list l is zero if the list is empty.
Otherwise, the sum is the value of the first item plus the sum of
the rest of the items in the list.Am I missing something? What does this have to do with summing?
>>def f(l):
... if l == []:
... return []
... else:
... return f(l[1:]) + l[:1]
...>>f([1, 2, 3, 4])
[4, 3, 2, 1]
Ian
这篇关于递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
