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 3A 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.
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:
[[]]
magic_list(0) blows the stack.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.
n <= 0, we return the empty array/list [].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)].n == 2, we return [[], [[]]]. The loop call looks like [fn(0), fn(1)], and we know fn(1) returns [[]], giving [[], [[]]].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?
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
