Hi,
I wrote this wrong recursive function that flattens a list:
def flatten(lst, acc=[]):
#print 'acc =', acc, 'lst =', lst
if type(lst) != list:
acc.append(lst)
else:
for item in lst:
flatten(item)
return acc
a = [1, 2, [3, 4, 5], [6, [7, 8, [9, 10], 11], 12], 13, 14]
b = flatten(a)
print b
I was amazed to realize that it flattens the list alright. Why? 'acc'
should be an empty list on each invocation of flatten, but is seems to
accumulate anyway... 5 947
On Jul 15, 2:59*pm, iu2 <isra...@elbit. co.ilwrote:
Hi,
I wrote this wrong recursive function that flattens a list:
def flatten(lst, acc=[]):
* * #print 'acc =', acc, 'lst =', lst
* * if type(lst) != list:
* * * * acc.append(lst)
* * else:
* * * * for item in lst:
* * * * * * flatten(item)
* * return acc
a = [1, 2, [3, 4, 5], [6, [7, 8, [9, 10], 11], 12], 13, 14]
b = flatten(a)
print b
I was amazed to realize that it flattens the list alright. Why? 'acc'
should be an empty list on each invocation of flatten, but is seems to
accumulate anyway...
When you say acc=[] in the function declaration, it binds acc to a
particular list object, rather than to a concept of an empty list.
Thus, all operations being performed on acc are being performed on the
same list. If, after the sample code you provided, were to call
c = flatten([15,16,17,[18,19]])
print c
you would get back the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13, 14, 15, 16, 17, 18, 19].
Mark Sherry
On Jul 15, 9:30*pm, mdshe...@gmail. com wrote:
On Jul 15, 2:59*pm, iu2 <isra...@elbit. co.ilwrote:
Hi,
I wrote this wrong recursive function that flattens a list:
def flatten(lst, acc=[]):
* * #print 'acc =', acc, 'lst =', lst
* * if type(lst) != list:
* * * * acc.append(lst)
* * else:
* * * * for item in lst:
* * * * * * flatten(item)
* * return acc
a = [1, 2, [3, 4, 5], [6, [7, 8, [9, 10], 11], 12], 13, 14]
b = flatten(a)
print b
I was amazed to realize that it flattens the list alright. Why? 'acc'
should be an empty list on each invocation of flatten, but is seems to
accumulate anyway...
When you say acc=[] in the function declaration, it binds acc to a
particular list object, rather than to a concept of an empty list.
Thus, all operations being performed on acc are being performed on the
same list. If, after the sample code you provided, were to call
c = flatten([15,16,17,[18,19]])
print c
you would get back the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13, 14, 15, 16, 17, 18, 19].
Mark Sherry
I still don't understand: In each recursive call to flatten, acc
should be bound to a new [], shouldn't it? Why does the binding happen
only on the first call to flatten?
On Jul 15, 4:12*pm, iu2 <isra...@elbit. co.ilwrote:
On Jul 15, 9:30*pm, mdshe...@gmail. com wrote:
On Jul 15, 2:59*pm, iu2 <isra...@elbit. co.ilwrote:
Hi,
I wrote this wrong recursive function that flattens a list:
def flatten(lst, acc=[]):
* * #print 'acc =', acc, 'lst =', lst
* * if type(lst) != list:
* * * * acc.append(lst)
* * else:
* * * * for item in lst:
* * * * * * flatten(item)
* * return acc
a = [1, 2, [3, 4, 5], [6, [7, 8, [9, 10], 11], 12], 13, 14]
b = flatten(a)
print b
I was amazed to realize that it flattens the list alright. Why? 'acc'
should be an empty list on each invocation of flatten, but is seems to
accumulate anyway...
When you say acc=[] in the function declaration, it binds acc to a
particular list object, rather than to a concept of an empty list.
Thus, all operations being performed on acc are being performed on the
same list. If, after the sample code you provided, were to call
c = flatten([15,16,17,[18,19]])
print c
you would get back the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13, 14, 15, 16, 17, 18, 19].
Mark Sherry
I still don't understand: In each recursive call to flatten, acc
should be bound to a new [], shouldn't it? Why does the binding happen
only on the first call to flatten?
Default values are bound when the function is defined, not when it's
called. For example,
>>import random def foo(bar = random.random() ):
... print bar
...
>>foo()
0.6323125498213 12
>>foo()
0.6323125498213 12
If you view [...] just as shorthand for list(...), it might make a bit
more sense. For immutable values, one can't change the value bound to
the name, only what the name is bound to, so this behaviour is less
obvious. But still there.
As to why default values are evaluated at define time vs. call time,
I'd argue reasons of scope and speed - if the default value is a
computed constant, it makes little sense to recompute it every time
the function is called.
Mark Sherry
iu2 wrote:
I still don't understand: In each recursive call to flatten, acc
should be bound to a new [], shouldn't it? Why does the binding happen
only on the first call to flatten?
Nope. In each new call it's (re)bound to the same original list, which
you've added to as your function continues--it's mutable. Default
variables that are bound to mutable objects are one of the big caveats
that is mentioned in the FAQ.
On Jul 16, 2:21*am, Michael Torrie <torr...@gmail. comwrote:
iu2 wrote:
I still don't understand: In each recursive call to flatten, acc
should be bound to a new [], shouldn't it? Why does the binding happen
only on the first call to flatten?
Nope. *In each new call it's (re)bound to the same original list, which
you've added to as your function continues--it's mutable. *Default
variables that are bound to mutable objects are one of the big caveats
that is mentioned in the FAQ.
Thanks guys, it's clear now This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Narendra C. Tulpule |
last post by:
Hi,
is there any way to allow recusrion in compile()? Something like:
src_code = 'def fact(n):\n\tif n <= 1:\n\t\treturn 1\n\telse:' + \
'\n\t\treturn n * fact(n-1)\n\nprint fact(12)\n'
cobj = compile(src_code, 'myfile', 'exec')
eval(cobj)
I did a search on 'recursion' in comp.lang.python but didn't turn up
anything relevant. Maybe I've highhhhhh expectations :-)
|
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: csx |
last post by:
Hi all,
Ive got a problem with recursion in Javascript.
For this tree:
http://www.pcm.uklinux.net/structure.jpg
If you input node 3 (i.e. C) which is represented as 'values' in the
array, it should return all the 'leaf' nodes. In this case 4!
Node 4 (i.e. D) is not included in the count.
|
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: 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: 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: Sylaris |
last post by:
hi, i have a problem which recursion fits perfectly, however; after working with the base function (which has no errors and works correctly) the recursions return a "function not defined" error in ff's js console. i tried a few things that came to mind but nothing has changed it... i found some interesting articles on the net regarding javascript's callbacks, and found out that due to callbacks recursion may end up eating a lot more memory than...
|
by: Mumia W. |
last post by:
Hello all.
I have a C++ program that can count the YOYOs that are in a grid of
Y's and O's. For example, this
Y O Y O O Y
O Y O Y O O
Y O Y Y O Y
O Y O O Y O
O Y Y O Y O
|
by: =?Utf-8?B?c2VlbWE=?= |
last post by:
Write a function that produces the same output as MyFunction but without the
use of recursion.
( perfect C# is not a requirement, you may write in pseudo code )
|
by: slix |
last post by:
Recursion is awesome for writing some functions, like searching trees
etc but wow how can it be THAT much slower for computing fibonacci-
numbers?
is the recursive definition counting fib 1 to fib x-1 for every x? is
that what lazy evaluation in functional languages avoids thus making
recursive versions much faster?
is recursive fibonacci in haskell as fast as an imperative solution in
a procedural language?
|
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: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
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: 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: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| | |