Understanding how is a function evaluated using recursion

[rusi]

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)))