递归

Can someone explain me thisif l == []:return []else:return f(l[1:]) + l[:1] # <= cant figure this, how is all sum at the end?thanks! 解决方案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 Iguess you''re trying to get a handle on recursion rather than just reverse alist. I find thinking up from the base case helps when trying tounderstand recursive code but when writing it, I tend to work the other wayaround.--I''m at CAMbridge, not SPAMbridgeif 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 ofthe 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 onenumber, 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 0else:return seq[0] + my_sum(seq[1:])The tough part of recursion is the leap of faith required tobelieve that it works. However, you can often use an inductiveproof of correctness to help obviate the faith.Proof that my_sum(seq) computes the sum of the items in seq (thisproof is modeled on proofs written by Max Hailperin, BarbaraKaiser, and Karl Knight, in _Concrete Abstractions_):Base case: my_sum(seq) terminates with value 0 when len(seq) iszero, because of the evaluation rules for if, len and ==.Induction hypothesis: Assume that my_sum(subseq) evaluates tothe sum of all the items in subsequence of seq, where 0 <=len(subseq) < len(seq).Inductive step: Consider evaluating my_sum(seq) where thelength of seq is greater than 0. This will terminate ifmy_sum(seq[1:]) terminates, and will have the value of seq[0] +my_sum(seq[1:]). Because seq[1:] evaluates to the subsequence ofthe rest of the items in seq (all except the first), and 0 <=len(subseq) < len(seq), we can assume by our inductionhypothesis that my_sum(seq[1:]) does terminate, with a valueequal to the sum of the the rest of the items in seq.Therefore, seq[0] + my_sum(seq[1:]) evaluates to seq[0] + thesum of all the items in seq[1:]. Because seq[0] + the sum ofthe rest of the items in seq equals the sum of all the items inseq, we see that my_sum(seq) does terminate with the correctvalue for any arbitrary length of seq, under the inductivehypothesis of correct operation for subsequences of seq.Conclusion: Therefore, by mathematical induction on the lengthof seq, my_sum(seq) terminates with the value of the sum of allthe items in seq for any length of seq.But really I prefer the first first plain English version. ;)--Neil CeruttiFor those of you who have children and don''t know it, we have a nurserydownstairs. --Church Bulletin Blooperif 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 ofthe rest of the items in the list.Am I missing something? What does this have to do with summing?... if l == []:... return []... else:... return f(l[1:]) + l[:1]...[4, 3, 2, 1]Ian 这篇关于递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！