In lecture 13 professor Guttag defined something like this:

def fibfast(n, memo):
print memo
if n in memo.keys():
return memo[n]
else:
memo[n] = fibfast(n-1, memo) + fibfast(n-2, memo)
return memo[n]

def fibl(n):
memo = {0:0, 1:1}
return fibfast(n, memo)

It works... thats fine.
The problem is that in theory when you call a function the variables are "local" and global variables have no effect. But what I'm seeing here is that memo is being modifided by the function.
For example:
you call
fastfib(8,{0:1,1:1})
then it tries to define:
memo[8] = fastfib(7, {0:1,1:1, 8:_} ) + fastfib

Question

In lecture 13 professor Guttag defined something like this:

def fibfast(n, memo):
	print memo
	if n in memo.keys():
		return memo[n]
	else:
		memo[n] = fibfast(n-1, memo) + fibfast(n-2, memo)
		return memo[n]

def fibl(n):
	memo = {0:0, 1:1}
	return fibfast(n, memo)

It works... thats fine.
The problem is that in theory when you call a function the variables are "local" and global variables have no effect. But what I'm seeing here is that memo is being modifided by the function.
For example:
you call
fastfib(8,{0:1,1:1})
then it tries to define:
memo[8] = fastfib(7, {0:1,1:1, 8:_} ) + fastfib

anonymous · Answer

Just watched the lecture too and not sure what your question is.  The function is supposed to modify the memo, thats how it 'remembers' and doesnt need to calculate that value again.

anonymous · Answer

mmm.... good. Another example:

def fun2(n, lis):
	lis = lis + [n,]
	if n == 1:
		return n
	else:
		a = fun2(n-1, lis)
		print lis
		return a
	

def fun1(n):
	li = []
	fun2(n, li)
	
fun1(8)

According to what I understand from lecture 13 this code should modify lis from the call:
fun2(8,[])
 and when it ends it should print lis = [1,2,3,4,5,6,7,8] eight times. But the last time it prints lis it prints: [8,].
So again. Why Professor Guttag's code work in that funky way.?

anonymous · Answer

here is what you were trying to do with fun1/2 http://dpaste.com/607712/ notice that in the "if n == 1" statement i returned the list, not the number python passes arguments "by reference" this might help: http://python.net/~goodger/projects/pycon/2007/idiomatic/handout.html#other-languages-have-variables

anonymous · Answer

"by reference" ?
That's hard....
So if I use a method for a mutable object when using recursion I will get a result like that?

anonymous · Answer

without thinking too hard i'm gonna say yes - it can work for you or against you. if you don't want your functions to modify/mutate an object, make a copy of it. in fact ps5 problem 3 had a constraint that the function was not supposed to mutate the object passed to it. you have to be really careful with mutable arguments with default values http://docs.python.org/tutorial/controlflow.html#default-argument-values http://python.net/~goodger/projects/pycon/2007/idiomatic/handout.html#default-parameter-values

anonymous · Answer

Ok, Thank you!