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! 15  1446 
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
Ian Clark wrote:
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
Add it up!
Round Sum
0 f([1, 2, 3, 4])
1 f([2, 3, 4]) + [1]
2 f([3, 4]) + [2] + [1]
3 f([4]) + [3] + [2] + [1]
4 f([]) + [4] + [3] + [2] + [1]
Total [] + [4] + [3] + [2] + [1] = [4, 3, 2, 1]
James
On 2007-09-13, Ian Clark <ic****@mail.ew u.eduwrote:
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]
It says: You need to read more than the first sentence of a
message before responsing:
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:])
--
Neil Cerutti
sorry i think that i express wrong. having problem with english
what i mean is how python knows to add all thing at the end of recursion
>>def f(l):
if l == []:
return []
else:
return f(l[1:]) + l[:1]
f([1,2,3])
recursion1 f([2,3]) + [1]
recursion2 f([3]) + [2] or [2, 1]?
recursion3 f([]) + [3] or [3, 2, 1]
i dont get all this
>>def f(l):
if l == []:
print l
return []
else:
return f(l[1:]) + l[:1]
>>f([1,2,3])
[]
[3, 2, 1] # how this come here? how python save variables from each recursion?
sorry again for first post
thanks
On Fri, 14 Sep 2007 13:40:17 +0200, Gigs_ wrote:
sorry i think that i express wrong. having problem with english
what i mean is how python knows to add all thing at the end of recursion
Because you have written code that tells Python to do so. ;-)
>>def f(l):
if l == []:
return []
else:
return f(l[1:]) + l[:1]
f([1,2,3])
recursion1 f([2,3]) + [1]
recursion2 f([3]) + [2] or [2, 1]?
recursion3 f([]) + [3] or [3, 2, 1]
Both alternatives in recursion 2 and 3 are wrong. You have to simply
replace the function invocation by its result which gives:
f([1, 2, 3])
r1 f([2, 3]) + [1]
r2 f([3]) + [2] + [1]
r3 f([]) + [3] + [2] + [1]
r4 [] + [3] + [2] + [1]
And now the calls return:
r3 [3] + [2] + [1]
r2 [3, 2] + [1]
r1 [3, 2, 1]
i dont get all this
>>def f(l):
if l == []:
print l
return []
else:
return f(l[1:]) + l[:1]
>>f([1,2,3])
[]
[3, 2, 1] # how this come here? how python save variables from each
recursion?
There is not just one `l` but one distinct `l` in each call.
Ciao,
Marc 'BlackJack' Rintsch
Gigs_ wrote:
sorry i think that i express wrong. having problem with english
what i mean is how python knows to add all thing at the end of recursion
>>def f(l):
if l == []:
return []
else:
return f(l[1:]) + l[:1]
f([1,2,3])
recursion1 f([2,3]) + [1]
recursion2 f([3]) + [2] or [2, 1]?
recursion3 f([]) + [3] or [3, 2, 1]
i dont get all this
>>def f(l):
if l == []:
print l
return []
else:
return f(l[1:]) + l[:1]
>>f([1,2,3])
[]
[3, 2, 1] # how this come here? how python save variables from each recursion?
sorry again for first post
I think the thing you are missing is that the recursive call f(l[1:]) in
the return statement causes the current call to be suspended until the
recursive call is complete. The new call has its own value for l, which
is the caller's l[1:]. Each new call creates a completely new namespace.
A less complicated function might make it a little more obvious.
def factorial(n):
print "n =", n
if n=0:
return 1
else:
return n * factorial(n-1)
Try running that with a few different arguments to show you how the
recursion works.
regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
Sorry, the dog ate my .sigline
On Sep 14, 10:04 pm, Marc 'BlackJack' Rintsch <bj_...@gmx.net wrote:
On Fri, 14 Sep 2007 13:40:17 +0200, Gigs_ wrote:
sorry i think that i express wrong. having problem with english
what i mean is how python knows to add all thing at the end of recursion
Because you have written code that tells Python to do so. ;-)
>>def f(l):
if l == []:
return []
else:
return f(l[1:]) + l[:1]
f([1,2,3])
recursion1 f([2,3]) + [1]
recursion2 f([3]) + [2] or [2, 1]?
recursion3 f([]) + [3] or [3, 2, 1]
Both alternatives in recursion 2 and 3 are wrong. You have to simply
replace the function invocation by its result which gives:
f([1, 2, 3])
r1 f([2, 3]) + [1]
r2 f([3]) + [2] + [1]
r3 f([]) + [3] + [2] + [1]
r4 [] + [3] + [2] + [1]
And now the calls return:
r3 [3] + [2] + [1]
r2 [3, 2] + [1]
r1 [3, 2, 1]
i dont get all this
>>def f(l):
if l == []:
print l
return []
else:
return f(l[1:]) + l[:1]
>>f([1,2,3])
[]
[3, 2, 1] # how this come here? how python save variables from each
recursion?
There is not just one `l` but one distinct `l` in each call.
I reckon that what the OP wants is a simple explanation of how
function calls use a stack mechanism for arguments and local
variables, and how this allows recursive calls, unlike the good ol'
FORTRAN IV of blessed memory. Perhaps someone could oblige him?
I'd try but it's time for my beauty sleep :-)
<yawn>
Good night all
John This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Peri |
last post by:
I'm trying to create Python parser/interpreter using ANTLR.
Reading grammar from language refference I found:
or_expr::= xor_expr | or_expr "|" xor_expr
For me it looks like infinite recursion. And so it says ANTLR. Maybe I
don't understand EBNF notation. For me it should look like this.
or_expr::= xor_expr | xor_expr "|" xor_expr
and in ANTLR grammar file like this:
|
by: da Vinci |
last post by:
Greetings.
I want to get everyone's opinion on the use of recursion.
We covered it in class tonight and I want a good solid answer from
people in the "know" on how well recursion is accepted in modern day
applications.
Should we readily use it when we can or only when absolutly forced to
use it?
|
by: Lorenzo Villari |
last post by:
I've tried to transform this into a not recursive version but without
luck...
#include <stdio.h>
void countdown(int p)
{
int x;
|
by: Csaba Gabor |
last post by:
I suppose spring fever has hit at alt.math.undergrad since I didn't get
any rise from
them when I posted this a week ago, so I am reposting this to some of
my favorite
programming groups:
I'm looking for problems that have double (or more) recursion, where
the split is not
clean (ie. where there may be overlap). Let's call this overlapped
recursion, where the
|
by: Sathyaish |
last post by:
Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?
I tried one example, and am in the process of trying out more examples,
increasing their complexity as I go. Here's a simple one I tried out:
#include<stdio.h>
/* To compare the the time and space cost of iteration against
| | |
by: Kay Schluehr |
last post by:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
|
by: MTD |
last post by:
Hello all,
I've been messing about for fun creating a trial division factorizing
function and I'm naturally interested in optimising it as much as
possible.
I've been told that iteration in python is generally more
time-efficient than recursion. Is that true?
Here is my algorithm as it stands. Any suggestions appreciated!
|
by: robert |
last post by:
My code does recursion loops through a couple of functions. Due to problematic I/O input this leads sometimes to "endless" recursions and after expensive I/O to the Python recursion exception.
What would be a good method to detect recursion loops and stop it by user-Exception (after N passes or some complex criteria) without passing a recursion counter parameter through all the funcs?
Robert
|
by: athar.mirchi |
last post by:
..plz define it.
|
by: Muzammil |
last post by:
int harmonic(int n) {
if (n=1) {
return 1;
}
else {
return harmonic(n-1)+1/n;
}
}
can any help me ??
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
| | |
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
| | |
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
