How do you append results to a list using recursion?

For example, using a basic factorial def:

def fact(n):
if n == 0: return 1
return n * fact(n-1)

This will return the "end" result, but what if I wanted to return a list of all the factorials... so that fact(5) would return [1, 1, 2, 6, 24, 120]?

This is a specific question about a general problem of variables or lists getting "reinitialized" every time during a recursive call!

For example: (SPOILER ALERT):

In 2008 PS4, this code will return the value of the *last* year:

def nestEggFixed(salary, save, growthRate, years):
if years == 1: return salary*(save/100.0) #base case, return annual contrib.
return salary*(save/100.0) + (1+growthRate/100.0)*nestEggFixed(salary,save,growthRate,(years-1))
# ^ each year adds annual contribution + interest*accumulated total

But the assignment wants a [list] for values after each year. This was easily done iteratively by appending result to a list during each loop, but recursively seems a lot harder...

Question

How do you append results to a list using recursion?

For example, using a basic factorial def:

def fact(n):
   if n == 0: return 1
   return n * fact(n-1)

This will return the "end" result, but what if I wanted to return a list of all the factorials... so that fact(5) would return [1, 1, 2, 6, 24, 120]?

This is a specific question about a general problem   of variables or lists getting "reinitialized" every time during a recursive call!

For example:  (SPOILER ALERT):

In 2008 PS4, this code will return the value of the *last* year:

def nestEggFixed(salary, save, growthRate, years):
    if years == 1: return salary*(save/100.0)  #base case, return annual contrib.
    return salary*(save/100.0) + (1+growthRate/100.0)*nestEggFixed(salary,save,growthRate,(years-1))
            # ^ each year adds annual contribution + interest*accumulated total

But the assignment wants a [list] for values after each year.  This was easily done iteratively by appending result to a list during each loop, but recursively seems a lot harder...

rsmith6559 · Answer

It isn't really.  You could pass in the list (empty at first) and as each recursion returns, it appends/prepends to the list.  Take a simple recursion like reversing a word, which is a string, which is a list of characters.

anonymous · Answer

so for the factorial example, what would the code look like?

def fact(n):
  if n == 0 return: [1]
  return [] + [fact(n-1]

This seemed reasonable to me, but in fact (excuse the pun!) doesn't work!

anonymous · Answer

http://dpaste.com/917357/

anonymous · Answer

Wow... those are some really neat ideas... not immediately intuitive to me, though... which is why recursive methods while elegant in execution, seem more complex to construct (IMHO)

anonymous · Answer

they were't intuitive to me either, i had to work it out and it took several tries.  i usually start by writing out in text what i am trying to accomplish and the steps/actions/resources it will take to accomplish it - then try to make that into code then debug it.

anonymous · Answer

Yeah... me too... only when I think it through that way, the iterative method seems to jump out at me and I have to 'force' myself to try to think of it recursively...

But many kudos for your efforts!  I had a feeling you might be able to do it with "sub functions"...

anonymous · Answer

well ... the functions i wrote are recursive procedures but they are iterative processes

anonymous · Answer

here is one that is a recursive process - it builds up a chain of deferred operations i used the code from your second post :) it's pretty clean - not as messy as the others i posted http://dpaste.com/918529/

anonymous · Answer

seems like the code is inching closer to the 'ideal' that I envision (if it even exists?!?)... but I'm not sure the output is correct... fa(5) gives me:

[5, 20, 60, 120, 120]

whereas I was hoping for [1,1,2,6,24,120]