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  1397 
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.ewu.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.netwrote:
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
Steve Holden wrote:
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
>>def factorial(n):
print "n =", n
if n==0:
return 1
else:
return n * factorial(n-1)
>>factorial(3)
n = 3
n = 2
n = 1
n = 0
6
now i understand. but one question at the end this function return 1. how python
knows that it needs to multiply 1 with all recursive returns. (why python didnt
sum recursive return with 1?)
that will be all, thanks in advance
On Fri, Sep 14, 2007 at 01:40:17PM +0200, Gigs_ wrote regarding Re: recursion:
>
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]
The following script does exactly the same thing, except it creates print
statements to help you figure out what's going on, and it binds f(L[1:]) to
a variable so you can use it again.
def f(L): # l capitalized to accentuate difference between l and 1.
print "L =", L
print "L[1:] =", L[1:]
print "L[:1] =", L[:1]
if L == []:
print "Return: ", []
return []
else:
next = f(L[1:])
print "Return: ", next, "+", L[:1], "=", next + L[:1]
return next + L[:1]
if __name__=='__main__':
print f(['A', 'B', 'C', 'D'])
Try it out. See what happens.
Cheers,
Cliff
On 2007-09-14, John Machin <sj******@lexicon.netwrote:
On Sep 14, 10:04 pm, Marc 'BlackJack' Rintsch <bj_...@gmx.netwrote:
>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
I may as well stick my neck out again, since I'm already
beautiful. ;)
Another way of understanding recursion is to break it up into
seperate functions, so the spectre of a function calling itself
doesn't appear.
def f(l):
if l == []:
return []
else:
return f(l[1:]) + l[:1]
The function above reverses a list of arbitrary length. To help
understand how it works, I'll write several discreet functions
that sort lists of fixed lengths.
I start with a simple case (though not the simplest case--that
only comes with experience), reversing a two-element list:
def f2(l): # reverse a two-element list
return [l[1], l[0]]
Next build up to the next level, writing a function that can
reverse a three-element list. The key is to be as lazy as
possible. You must figure out a way of taking advantage of the
function that reverses a two-element list. The obvious solution
is to use f2 to reverse the last two elements in our list, and
append the first element in the list to that result:
def f3(l): # reverse a three-element list
return f2(l[1:]) + l[:1]
And so on:
def f4(l):
return f3(l[1:]) + l[:1]
def f5(l):
return f4(l[1:]) + l[:1]
def f6(l):
return f5(l[1:]) + l[:1]
A definite pattern had emerged, and it should be apparent now how
to combine all those functions into one:
def f_(l):
if len(l) == 2:
return [l[1], l[0]]
else:
return f_(l[1:]) + l[:1]
But the function above breaks for lists with less than two items.
>>f_([1])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 2, in f2
IndexError: list index out of range
We can handle that. The reverse of a zero or one-element list is
just itself.
def f_(l):
if len(l) < 2:
return l
elif len(l) == 2:
return [l[1], l[0]]
else:
return f_(l[1:]) + l[:1]
And we've arrived at an OK recursive function that can handle
arbitrary length lists. It's not as simple as it could be,
however. A little intuitive leap, perhaps, will allow you to note
that the case of a two-element list can actually be handled
without a special case:
def f(l):
if len(l) < 2:
return l
else:
return f(l[1:]) + l[:1]
Final note: for reasons of tradition, base cases are almost
always set up as it was in the original function, checking for a
zero-length list, and returning a new empty list, the truly
simplest base case. Another intuitive leap is possibly required
to note that a one-element list is not a special case after all:
it's a reverse of a zero-element list with that one element
appended.
def f(l):
if len(l) == 0:
return []
else:
return f(l[1:]) + l[:1]
Clear as mud?
--
Neil Cerutti
On Fri, 14 Sep 2007 15:58:39 +0200, Gigs_ wrote:
>>def factorial(n):
print "n =", n
if n==0:
return 1
else:
return n * factorial(n-1)
>>factorial(3)
n = 3
n = 2
n = 1
n = 0
6
now i understand. but one question at the end this function return 1. how python
knows that it needs to multiply 1 with all recursive returns. (why python didnt
sum recursive return with 1?)
Because there is a ``*`` and not a ``+`` in the last line of the function.
Let's play this through (I abbreviate the function name to just `f()`):
Execution of f(3) leads to the second return:
r1 f(3): return 3 * f(2)
This multiplication can't take place until ``f(2)`` is calculated so the
current function call is "suspended" and evaluated later, when the result
of ``f(2)`` is known. The call in that line is replaces with the result
then. Calling ``f(2)`` leads to:
r2 f(2): return 2 * f(1)
The same again, another call to `f()` with 1 as argument:
r3 f(1): return 1 * f(0)
Now the last call takes the other ``if`` branch:
r4 f(0): return 1
The 1 is returned to the previus call:
r3 f(1): return 1 * 1
This can be evaluated now and is returned to its caller:
r2 f(2): return 2 * 1
Again this is evaluated and returned to its caller:
r1 f(3): return 3 * 2
And here we have the final result that is returned from the first call to
`f()`.
Ciao,
Marc 'BlackJack' Rintsch
"Marc 'BlackJack' Rintsch" <bj****@gmx.netwrote in message
news:5k************@mid.uni-berlin.de...
| f([1, 2, 3])
| r1 f([2, 3]) + [1]
| r2 f([3]) + [2] + [1]
| r3 f([]) + [3] + [2] + [1]
| r4 [] + [3] + [2] + [1]
I might help to note that the above is effectively parenthesized
( ( ([]+{3]) + [2]) +[1])
*and* that each addition (in each pair of parentheses) is done
in a different execution frame (see below).
| And now the calls return:
|
| r3 [3] + [2] + [1]
| r2 [3, 2] + [1]
| r1 [3, 2, 1]
| [3, 2, 1] # how this come here? how python save variables from each
| recursion?
*Each time* a function is called, an execution frame is created(1) that is
separate from the function object itself. Each execution frame has its own
set of local variables. In particular, each has its own slices of the
original list.
There have been languages, for instance, Fortran IV, where local variables
were part of the function 'object' and which therefore prohibited recursion
because of the very problem you alluded to in your question. (My guess is
the functions had an InUse flag that was checked when the function was
called.)
tjr
(1) A minor variation would be for function objects to have one
pre-allocated execution frame for non-recursive calls and others allocated
as needed for recursive calls.
On Sep 15, 3:06 am, "Terry Reedy" <tjre...@udel.eduwrote:
>
There have been languages, for instance, Fortran IV, where local variables
were part of the function 'object' and which therefore prohibited recursion
because of the very problem you alluded to in your question. (My guess is
the functions had an InUse flag that was checked when the function was
called.)
No way. Waste of space for instructions to check the flag at the start
and reset it at the end. Waste of CPU time. Divide by zero? Subroutine
calls itself? Drive against the traffic flow on the freeway? Expected
outcome: crash or other unwanted result. Simple: don't do that! Why
bother checking? No self-respecting FORTRAN programmer would want to
use recursion anyway. And mixed case in a variable name? Sheesh. 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....
|
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...
|
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...
|
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...
|
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...
|
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...
|
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: lllomh |
last post by:
Define the method first
this.state = {
buttonBackgroundColor: 'green',
isBlinking: false, // A new status is added to identify whether the button is blinking or not
}
autoStart=()=>{
|
by: DJRhino |
last post by:
Was curious if anyone else was having this same issue or not....
I was just Up/Down graded to windows 11 and now my access combo boxes are not acting right. With win 10 I could start typing...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 4 Oct 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM)
The start time is equivalent to 19:00 (7PM) in Central...
|
by: Aliciasmith |
last post by:
In an age dominated by smartphones, having a mobile app for your business is no longer an option; it's a necessity. Whether you're a startup or an established enterprise, finding the right mobile app...
|
by: giovanniandrean |
last post by:
The energy model is structured as follows and uses excel sheets to give input data:
1-Utility.py contains all the functions needed to calculate the variables and other minor things (mentions...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 1 Nov 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM)
Please note that the UK and Europe revert to winter time on...
|
by: nia12 |
last post by:
Hi there,
I am very new to Access so apologies if any of this is obvious/not clear.
I am creating a data collection tool for health care employees to complete. It consists of a number of...
|
by: NeoPa |
last post by:
Introduction
For this article I'll be focusing on the Report (clsReport) class. This simply handles making the calling Form invisible until all of the Reports opened by it have been closed, when it...
|
by: GKJR |
last post by:
Does anyone have a recommendation to build a standalone application to replace an Access database? I have my bookkeeping software I developed in Access that I would like to make available to other...
| |
