Recursive function that return a list

I want to know how to do the second function recursively.

def sum(x):
    if x == 1:
        return 1
    else:
        return sum(x-1) + x
    
def factorials(x):
    list1 = []
    for c in range(1, x+1):
        list1.append(sum(c))
    return list1

print(factorials(10))

in the first function, you pass n as an argument and return the sum of 1 + 2 + 3 + ... + n

in the second function you will return a list of n sums, for example when you invoke factorial(10), the output is gonna be [1, 3, 6, 10, 15, 21, 28, 36, 45, 55].

My real problem is that I wanna know if have some way to do the second function in a recursive way. I am struggling with list appends in recursive functions.

Several answers have shown you how you can have your (misleadingly named) factorial function produce a list by calling itself and the (also misleadingly named) sum function. But nobody has yet noted that calling sum repeatedly, as this algorithm will do, is extremely wasteful. You keep needing to recurse up a chain of sum calls at every level of the factorial recursion.

Instead, you should rewrite your factorial to directly compute the newest values based on the previous values in the list (found recursively)! Here's what that looks like:

def factorial(n):
    """Returns a list of the first n triangular numbers"""
    if n <= 0:        # this base case is just for general safety
        return []
    if n == 1:        # this is the main base case, where our recursion ends
        return [1]

    lst = factorial(n-1)  # recurse, get a list back with n-1 values
    nth_value = lst[-1]+n # compute the nth value based on the (n-1)th value
    lst.append(nth_value) # add the value to the end of the list
    return lst

Replace lst[-1]+n with lst[-1]*n if you actually want the first n factorials, rather than the first n triangular numbers.

As pointed out by @SimonUnderwood in the comments, this is computing triangular numbers, not factorial. That being said, here's some code:

def triangulars(x):
    if x < 1:
        return []
    return triangulars(x - 1) + [sum(x)]

The trick is to append an item to the list in each recursive call. In this case, I'm doing it by creating a new list with sum for the current number and using the addition operator on lists to combine it with the list for the number below it.

First an observation: do not name a function sum since that is a built-in function in python.

The solution lies in declaring a list OUTSIDE of the recursive function, and you don't need a sum or equivalent function:

def factorials(limit):
	def fact(limit, count: int, alist: list):
		if count > limit:
			return
		alist.append(1 if len(alist) == 0 else alist[-1] + count)
		fact(limit, count + 1, alist)

	list1 = []
	fact(limit, 1, list1)
	return list1

print(factorials(10))

That produces [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]. Also note that this is also a more python-ish solution.

You could implement triangle using scan -

from operator import add

def triangle(x):
  return scan(add, 0, range(1, x + 1))

def scan(f, init, ls):
  if not ls:
    return [init]
  else:
    return [init] + scan(f, f(init, ls[0]), ls[1:])

print(triangle(10))
# [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

print(triangle(0))
# [0]

Since you're doing cumulative sums (not actual factorials), you could use the n(n+1)/2 formula (or your own sum() function) to compute each term:

def factorials(n): 
    return factorials(n-1) + [n*(n+1)//2] if n else []

or

def factorials(n): 
    return factorials(n-1) + [sum(n)] if n else []

Alternatively, you can pass down a partial result to the recursion and cascade the final list back up the return stack when n reaches zero. Each recursive call only needs to use the last value and current length to compute the next entry to add:

def factorials(n,r=[0]): 
    return factorials(n-1,r+[r[-1]+len(r)]) if n else r[1:]

Another way is to pass down a counter that increases up to n along with a last result value and concatenate the recursed list with the new entry (which can be computed forward using the counter):

def factorials(n,i=1,r=0): 
    return [] if i>n else [r+i]+factorials(n,i+1,r+i)

I fixed some variable naming to clarify and changed some conditions so that it would not infinitely loop if x <= 0

def triangle(x):
    if x <= 1:
        return x
    else:
        return triangle(x-1) + x
    

# Although it doesn't impact this particular example, it's generally not recommended to use lists as default values. 
def get_triangular_sequence(x, found = None):
    if found is None:
        found = []
    if x <= 1:
        found.append(x)
        return found
    found.append(triangle(x))
    return get_triangular_sequence(x-1, found)


print(get_triangular_sequence(10))

The list will be in greatest to least order, but it can be easily flipped if you so desire.

I would be remiss if I did not mention at the top that recursive functions are SERIOUSLY UNDERPERFORMANT in Python. You should avoid recursive solutions whenever possible when writing Python, as the iterative implementation is almost always faster and cheaper.

Recursive functions call themselves, returning either the recursive case or the base case. The base case will eventually bubble up and end recursion, producing your final value.

Consider, for instance, this recursively-defined factorial function:

def factorial(n: int) -> int:
    if n == 0:
        return 1  # this should only be possible to reach
                  # on the first round of recursion, and
                  # is more of an early-out than a base case
    elif n == 1:
        # base case
        return n
    elif n < 0:
        raise ValueError("Factorial for negative number")
    else:
        # recursive case
        return n * factorial(n-1)

After dealing with some edge cases (n=0, n<0), you have two cases left:

• Base case: if n == 1, stop recursing and return 1
• Recursive case: if n >= 2, multiple n by the next result of factorial(n-1)

If you wanted a function that recursively calculated each of a number of these, you could do...

# from typing import List
def factorial_range(start: int, stop: int, _cur=None) -> List[int]:
    if start >= stop:
        raise ValueError('Invalid range')
    if _cur is None:
        _cur = start
    if _cur == stop:
        # base case
        return []
    else:
        # recursive case
        return [factorial(_cur)] + factorial_range(start, stop, _cur+1)