Re: Understanding how is a function evaluated using recursion
On Thursday, September 26, 2013 4:54:22 AM UTC+5:30, Arturo B wrote: So I know what recursion is, but I don't know how is flatten(i) evaluated, what value does it returns? There is a folklore in CS that recursion is hard [To iterate is human, to recurse divine -- Peter Deutsch] This is unfortunate and inaccurate as students brought up on functional programming dont seem to find it hard. What is hard is mixing imperative programming and recursion. So here are some non-imperative versions of flatten # At first pull out the recursion-checking predicate def isrec(x): return isinstance(x, list) or isinstance(x, tuple) # And we need a cutdown version of flatten -- concat. # concat flattens exactly one level. More it does not go into, less and it errors out def concat(l): return [y for x in l for y in x] # Version 0 def flat0(l): if not isrec(l): return [l] else: return concat([flat0(i) for i in l]) # Push the if into the return -- more functional def flat1(l): return ([l] if not isrec(l) else concat([flat1(i) for i in l])) # push the if expression into the comprehension def flat2(l): return concat([flat2(i) if isrec(i) else [i] for i in l]) ### Lisp-y solution def hd(l) : return l[0] def tl(l) : return l[1:] def null(l): return l==[] def flat4(l): return ( [] if null(l) else [l] if not isrec(l) else flat4(hd(l)) + flat4(tl(l))) -- https://mail.python.org/mailman/listinfo/python-list
Re: Understanding how is a function evaluated using recursion
On Thursday, September 26, 2013 7:23:47 AM UTC-7, Neil Cerutti wrote: On 2013-09-26, Neil Cerutti ne...@norwich.edu wrote: def flatten(seq): [1] http://en.wiktionary.org/wiki/bikeshed In that spirit, it occurs to me that given current Python nomenclature, 'flattened' would be a better name. -- Neil Cerutti The example presented here is simple enough for someone who is confident with recursion and somewhat new to Python. So perhaps a refresher on recursion would help. The way to grok recursion for the first time is (a) to read some general info about it (Wikipedia has some decent stuff here, but there are many other sources) and (b) find a simple recursion example and play around with it in the debugger. Python has some decent debugger solutions - I like using ipdb with iPython. The factorial function is a good one to play around with if you're new to recursion. The Fibonacci sequence is also good. Find a .py example, or, better yet, write your own based on psuedo code. If you're a recursion expert already, then I don't know what to tell you other than Python seems to have implemented recursion faithfully and there are no gotchas that I can see. -- https://mail.python.org/mailman/listinfo/python-list
Re: Understanding how is a function evaluated using recursion
On 2013-09-25, Arturo B a7xrturo...@gmail.com wrote: Hi, I'm doing Python exercises and I need to write a function to flat nested lists as this one: [[1,2,3],4,5,[6,[7,8]]] To the result: [1,2,3,4,5,6,7,8] So I searched for example code and I found this one that uses recursion (that I don't understand): def flatten(l): ret = [] for i in l: if isinstance(i, list) or isinstance(i, tuple): ret.extend(flatten(i)) #How is flatten(i) evaluated? else: ret.append(i) return ret So I know what recursion is, but I don't know how is flatten(i) evaluated, what value does it returns? It only *looks* like magic, as others have explained. I keep a file callled bikeshed.py for these occasions. The flatten function has been to the bike shed a lot [1]. Here's a non-recursive version of flatten for comparison: from collections import Sequence def flatten(seq): stack = [] i = 0 result = [] while True: if i = len(seq): if stack: seq, i = stack.pop() else: return result elif isinstance(seq[i], Sequence): stack.append((seq, i+1)) # Store the continue point seq = seq[i] i = 0 else: result.append(seq[i]) i += 1 When this version encounters a nested list, it keeps a stack of sequences and indices to continue on with after processing the nested list. The code at the start of the while loop, when a sequence is exhausted, pops the continue points fromt he stack, returning if the stack is empty. It's simpler and cleaner to call flatten on itself, as in the recursive version, because the stack frames do all the bookkeeping for you. CPython has a limited number of stack frames though, so the version above might be preferable for certain levels of nesting. [1] http://en.wiktionary.org/wiki/bikeshed -- Neil Cerutti -- https://mail.python.org/mailman/listinfo/python-list
Re: Understanding how is a function evaluated using recursion
On 2013-09-26, Neil Cerutti ne...@norwich.edu wrote: def flatten(seq): [1] http://en.wiktionary.org/wiki/bikeshed In that spirit, it occurs to me that given current Python nomenclature, 'flattened' would be a better name. -- Neil Cerutti -- https://mail.python.org/mailman/listinfo/python-list
Understanding how is a function evaluated using recursion
Hi, I'm doing Python exercises and I need to write a function to flat nested lists as this one: [[1,2,3],4,5,[6,[7,8]]] To the result: [1,2,3,4,5,6,7,8] So I searched for example code and I found this one that uses recursion (that I don't understand): def flatten(l): ret = [] for i in l: if isinstance(i, list) or isinstance(i, tuple): ret.extend(flatten(i)) #How is flatten(i) evaluated? else: ret.append(i) return ret So I know what recursion is, but I don't know how is flatten(i) evaluated, what value does it returns? Thank you -- https://mail.python.org/mailman/listinfo/python-list
Re: Understanding how is a function evaluated using recursion
On Wednesday, September 25, 2013 4:24:22 PM UTC-7, Arturo B wrote: Hi, I'm doing Python exercises and I need to write a function to flat nested lists So I know what recursion is, but I don't know how is flatten(i) evaluated, what value does it returns? In this case, flatten always returns a list. When it hits the recursion, it calls itself to get another list, that it uses to extend the current list. Josh -- https://mail.python.org/mailman/listinfo/python-list
Re: Understanding how is a function evaluated using recursion
On 26/09/2013 00:24, Arturo B wrote: Hi, I'm doing Python exercises and I need to write a function to flat nested lists as this one: [[1,2,3],4,5,[6,[7,8]]] To the result: [1,2,3,4,5,6,7,8] So I searched for example code and I found this one that uses recursion (that I don't understand): def flatten(l): ret = [] for i in l: if isinstance(i, list) or isinstance(i, tuple): ret.extend(flatten(i)) #How is flatten(i) evaluated? else: ret.append(i) return ret So I know what recursion is, but I don't know how is flatten(i) evaluated, what value does it returns? Try a simpler version first: def flatten(l): ret = [] for i in l: if isinstance(i, list) or isinstance(i, tuple): # Append the contents of the item. ret.extend(i) else: # Append the item itself. ret.append(i) return ret In this example, flatten([[1,2,3],4,5,[6,[7,8]]]) returns [1,2,3,4,5,6, [7,8]]. The problem here is that a sublist can itself contain a list. It would be nice if there were a function which, when given [6,[7,8]], would return [6,7,8] so that you could append those items. But that's exactly what flatten does! Try adding prints to tell you what was passed in and what is returned. -- https://mail.python.org/mailman/listinfo/python-list
Re: Understanding how is a function evaluated using recursion
On Wed, 25 Sep 2013 16:24:22 -0700, Arturo B wrote: Hi, I'm doing Python exercises and I need to write a function to flat nested lists as this one: [[1,2,3],4,5,[6,[7,8]]] To the result: [1,2,3,4,5,6,7,8] So I searched for example code and I found this one that uses recursion (that I don't understand): def flatten(l): ret = [] for i in l: if isinstance(i, list) or isinstance(i, tuple): ret.extend(flatten(i)) #How is flatten(i) evaluated? else: ret.append(i) return ret So I know what recursion is, but I don't know how is flatten(i) evaluated, what value does it returns? You have the source code to flatten right there in front of you. The very last line says: return ret The first line of the function sets: ret = [] and it is a list which accumulates all the items seen. If you follow the code with a simple non-nested list: flatten([1, 2, 3]) flatten sets the return result ret to the empty list, then walks the argument list extracting each item in turn, which results in this sequence of calls: ret = [] ret.append(1) ret.append(2) ret.append(3) return ret # [1, 2, 3, 4] Now if we do the same thing with a nested list: flatten([1, [2, 3], 4]) the call to flatten does the same thing, walks the input list, only this time it has a recursive call: # outer call ret = [] ret.append(1) At this point, the item found is a list, so flatten([2, 3]) is called, so Python drops into into a new call, building a new list called ret, leaving the old one untouched: # inner call ret = [] ret.append(2) ret.append(3) return ret # [2, 3] At this point Python drops back to the first call again: # outer call ret.extend([2, 3]) ret.append(4) return ret # [1, 2, 3, 4] But it all together in one chunk, without the commentary: flatten([1, [2, 3], 4]) = # outer call ret = [] ret.append(1) flatten([2, 3]) = # inner call ret = [] ret.append(2) ret.append(3) return ret # [2, 3] # outer call ret.extend([2, 3]) ret.append(4) return ret # [1, 2, 3, 4] In principle, you can nest as many function calls as needed. In practice, Python will stop after 1000 nested calls by default, although you can tune it up and down. -- Steven -- https://mail.python.org/mailman/listinfo/python-list
Re: Understanding how is a function evaluated using recursion
On 25/9/2013 19:24, Arturo B wrote: Hi, I'm doing Python exercises and I need to write a function to flat nested lists as this one: [[1,2,3],4,5,[6,[7,8]]] To the result: [1,2,3,4,5,6,7,8] So I searched for example code and I found this one that uses recursion (that I don't understand): def flatten(l): ret = [] for i in l: I can't imagine why you'd use either i or l in this context, but especially use them both when they look so much alike. if isinstance(i, list) or isinstance(i, tuple): ret.extend(flatten(i)) #How is flatten(i) evaluated? else: ret.append(i) return ret So I know what recursion is, but I don't know how is flatten(i) evaluated, what value does it returns? flatten() returns a list, of course. The value of 'ret' in the inner function. What don't you understand about recursion? You write a function that's valid for the simple case (a simple list, with none of the elements being lists or tuples). Then you use that function inside itself to handle the more complex cases. -- DaveA -- https://mail.python.org/mailman/listinfo/python-list
Re: Understanding how is a function evaluated using recursion
On 9/25/2013 7:24 PM, Arturo B wrote: Hi, I'm doing Python exercises and I need to write a function to flat nested lists as this one: [[1,2,3],4,5,[6,[7,8]]] To the result: [1,2,3,4,5,6,7,8] So I searched for example code and I found this one that uses recursion (that I don't understand): def flatten(l): ret = [] for i in l: if isinstance(i, list) or isinstance(i, tuple): ret.extend(flatten(i)) #How is flatten(i) evaluated? else: ret.append(i) return ret So I know what recursion is, but I don't know how is flatten(i) evaluated, what value does it returns? It is not clear what part of 'how' you do not understand this. Perhaps that fact that a new execution frame with a new set of locals is created for each call. So calling flatten from flatten is no different than call flatten from anywhere else. If a language creates just one execution frame for the function, attached to the function (as with original Fortran, for instance), then recursion is not allowed as a 2nd call would interfere with the use of the locals by the 1st call, etc. -- Terry Jan Reedy -- https://mail.python.org/mailman/listinfo/python-list
Re: Understanding how is a function evaluated using recursion
On Thursday, September 26, 2013 4:54:22 AM UTC+5:30, Arturo B wrote: So I know what recursion is, but I don't know how is flatten(i) evaluated, what value does it returns? When you are a noob, who do you ask? The gurus. When you are a guru who do you ask? The computer! And its really quite easy to ask the computer directly. Here's your code with a extra prints def flatten(l): print (Received: %s % l) ret = [] for i in l: if isinstance(i, list) or isinstance(i, tuple): ret.extend(flatten(i)) #How is flatten(i) evaluated? else: ret.append(i) print (Returning: %s % ret) return ret Now run it with a couple of different inputs (not neglecting the trivial cases) and see if it does not self-explain. If still confusing, come back and ask! -- https://mail.python.org/mailman/listinfo/python-list
