-4

I've got an assignment in which I need to code a recursive function (with no loops) in Python that returns:

  • [[]] if n is 1
  • [[],[[]]] if n is 2
  • [[],[[]],[[],[[]]]] if n is 3

A pseudo code or a hint would be really appreciated.

My current code which I'm working on:

def ezr(n,a,b):
    a.append(b)
    b= deepcopy(a)
    return ezr(n-1,a,b)

def magic_list(n):
    return ezr(n,[],[])

I'm stuck with the first function.

ggorlen
  • 44,755
  • 7
  • 76
  • 106
Damn Lildamn
  • 1
  • 2

3 Answers3

0
def magic_list(n, a=[]):
    a.append(a.copy())

    if n - 1:
        return magic_list(n - 1, a)
    else:
        return a

for n = 3:

print(magic_list(3))

Output:

[[], [[]], [[], [[]]]]

for n = 2:

print(magic_list(2))

Output:

[[], [[]]]

for n = 1:

print(magic_list(1))

Output:

[[]]
Ze'ev Ben-Tsvi
  • 1,174
  • 1
  • 3
  • 7
  • See ["Least Astonishment" and the Mutable Default Argument](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument). Also, `magic_list(0)` blows the stack. – ggorlen Dec 10 '22 at 20:18
0

Here's pseudocode:

function f(n) {
  if (n <= 0) {
    return []
  }

  array = []

  for i = 0; i < n; i++ {
    array.push_back(f(i))
  }

  return array
}

Let's examine how this works.

  • The base case is when n <= 0, we return the empty array/list [].
  • When n == 1 we return [[]] because the loop runs one iteration, appending [] as the only element of the array = [] list we're building on this frame. The loop call looks like [fn(0)].
  • When n == 2, we return [[], [[]]]. The loop call looks like [fn(0), fn(1)], and we know fn(1) returns [[]], giving [[], [[]]].
  • When n == 3, we return [[], [[]], [[], [[]]]]. The loop call looks like [fn(0), fn(1), fn(2)], and we know that fn(0) expands to [], fn(1) expands to [[]] and fn(2) expands to [[], [[]]], giving [[], [[]], [[], [[]]]].

See also How to implement set-theoretic definition of natural numbers?

ggorlen
  • 44,755
  • 7
  • 76
  • 106
-1

Generally recursion is the thing you should follow, but you have to work yourself on exit condition and how to receive data from recursion stack.

For now I see there are two problems, your recursion is infinite (wouldn't work for any call). Second is gathering data from your stack.

This should be enough to give you a lead to solve it on your own :)

from copy import deepcopy

def magic_list(n,a=[], b=[]):
    if n == 1:
        return []
    a = deepcopy(b)
    a.append(magic_list(n-1,a,b))
    return a

print(magic_list(1)) # []
print(magic_list(2)) # [[]]
print(magic_list(3)) # [[[]]]

If you strugle with visualization, use pythontutor.com

Visualization of execution step by step of code above: https://pythontutor.com/visualize.html#code=%0Afrom%20copy%20import%20deepcopy%0A%0Adef%20magic_list%28n,a%3D%5B%5D,%20b%3D%5B%5D%29%3A%0A%20%20%20%20if%20n%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20return%20%5B%5D%0A%20%20%20%20a%20%3D%20deepcopy%28b%29%0A%20%20%20%20a.append%28magic_list%28n-1,a,b%29%29%0A%20%20%20%20return%20a%0A%0Aprint%28magic_list%281%29%29%20%23%20%5B%5D%0Aprint%28magic_list%282%29%29%20%23%20%5B%5B%5D%5D%0Aprint%28magic_list%283%29%29%20%23%20%5B%5B%5B%5D%5D%5D%0A&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false

Guaz
  • 34
  • 2