I apologize for asking such a trivial beginner question here but every time I go two steps forward with understanding recursion, I seem to be going three steps backwards. I can't figure out why this simple code to store n numbers in an array gives blanks. I can get it to work by doing the commented portion, but in the top portion that does not work, I assumed y and x will be populated when the stack frame unwinds and the array should return a list of numbers. Can someone please explain what is wrong with my assumption and how to visualize recursion and how to use the results while the calls are made recursively and when the return values propagate back to the main function?
def nums(n,x):
if n == 0:
return n
else:
y=(nums(n-1,x))
x.append(y)
return x # output was all blanks
# nums(n-1,x)
# x.append(n)
return x # This works
x=[]
print(nums(7,x))
CodePudding user response:
The way that we usually teach this with recursion is to do stack traces with different values to demonstrate the flow.
nums(0, []) => 0 # n.b., this is a scalar, not an array based on the code above
nums(1, []) =>
y = (nums(0, x)) => 0 (from above) # n.b., this might be interpreted as a tuple since we have surrounded it with parentheses, best to avoid enclosing parentheses if you don't need them
x.append(y) => x = [ 0 ]
return x => [ 0 ]
Now we get tricky because x is a list
, so it is passed by reference and returned. So for n > 1, we will be appending x to itself, which is what will cause the issue
nums(2, []) =>
y = nums(1, []) =>
y = nums(0, []) =>
y = 0
x = [ 0 ]
=> [ 0 ]
x.append(x = [ 0 ]) => yields a circular reference since we are appending x to itself
You may have intended to use stack unwind semantics, but if that was the intent we need fresh lists as local variables as we do the recursion:
def nums(n):
if n == 0:
return [ 0 ]
return [ n ] nums(n - 1)