Recursively generating a list of lists in a triangular format given a height and value

user_12279819 0
Viewed 285

I recently started looking into recursion to clean up my code and "up my game" as it were. As such, I'm trying to do things which could normally be accomplished rather simply with loops, etc., but practicing them with recursive algorithms instead.

Currently, I am attempting to generate a two-dimensional array which should theoretically resemble a sort of right-triangle in an NxN formation given some height n and the value which will get returned into the 2D-array.

As an example, say I call: my_function(3, 'a');, n = 3 and value = 'a'

My output returned should be: [['a'], ['a', 'a'], ['a', 'a', 'a']]

[['a'], 
 ['a', 'a'], 
 ['a', 'a', 'a']]

Wherein n determines both how many lists will be within the outermost list, as well as how many elements should successively appear within those inner-lists in ascending order.

As it stands, my code currently looks as follows:

def my_function(n, value):
    base_val = [value]
    if n == 0:
        return [base_val]
    else:
        return [base_val] + [my_function(n-1, value)]

Unfortunately, using my above example n = 3 and value = 'a', this currently outputs: [['a'], [['a'], [['a'], [['a']]]]]

Now, this doesn't have to get formatted or printed the way I showed above in a literal right-triangle formation (that was just a visualization of what I want to accomplish).

I will answer any clarifying questions you need, of course!

multidimensional-array recursion python-3.x python
4 Answers

You have a couple logic errors: off-by-1 with n, growing the wrong side (critically, the non-base implementation should not use a base-sized array), growing by an array of the wrong size. A fixed version:

#!/usr/bin/env python3


def my_function(n, value):
    if n <= 0:
        return []
    return my_function(n-1, value) + [[value]*n]


def main():
    print(my_function(3, 'a'))


if __name__ == '__main__':
    main()

Since you're returning mutable, you can get some more efficiency by using .append rather than +, which would make it no longer functional. Also note that the inner mutable objects don't get copied (but since the recursion is internal this doesn't really matter in this case).

It would be possible to write a tail-recursive version of this instead, by adding a parameter.

But python is a weird language for using unnecessary recursion.

user_14055880

The easiest way for me to think about recursive algorithms is in terms of the base case and how to build on that.

The base case (case where no recursion is necessary) is when n = 1 (or n = 0, but I'm going to ignore that case). A 1x1 "triangle" is just a 1x1 list: [[a]].

So how do we build on that? Well, if n = 2, we can assume we already have that base case value (from calling f(1)) of [[a]]. So we need to add [a, a] to that list.

We can generalize this as:

f(1)     = [[a]]
f(n > 1) = f(n - 1) + [[a] * n]

, or, in Python:

def my_function(n, value):
    if n == 1:
        return [[value]]
    else:
        return my_function(n - 1, value) + [[value] * n]
user_11597350

While the other answers proposed another algorithm for solving your Problem, it could have been solved by correcting your solution:

Using a helper function such as:

def indent(x, lst):
    new_lst = []
    for val in lst:
        new_lst += [x] + val
    return new_lst

You can implement the return in the original function as:

return [base_val] + indent(value, [my_function(n-1, value)])

The other solutions are more elegant though so feel free to accept them.

Image

Here is an image explaining this solution.

The red part is your current function call and the green one the previous function call.

As you can see, we also need to add the yellow part in order to complete the triangle.

Image2

These are the other solutions.

In these solutions you only need to add a new row, so that it's more elegant overall.

user_119428340 
return [base_val]

Okay, for n == 0 we get [[value]]. Solid. Er, sort of. That's the result with one row in it, right? So, our condition for the base case should be n == 1 instead.

Now, let's try the recursive case:

return [base_val] + [my_function(n-1, value)]

We had [[value]], and we want to end up with [[value], [value, value]]. Similarly, when we have [[value], [value, value]], we want to produce [[value], [value, value], [value, value, value]] from it. And so on.

The plan is that we get one row at the moment, and all the rest of the rows by recursing, yes?

  1. Which rows will we get by recursing? Answer: the ones at the beginning, because those are the ones that still look like a triangle in isolation.

  2. Therefore, which row do we produce locally? Answer: the one at the end.

  3. Therefore, how do we order the results? Answer: we need to get the result from the recursive call, and add a row to the end of it.

  4. Do we need to wrap the result of the recursive call? Answer: No. It is already a list of lists. We're just going to add one more list to the end of it.

  5. How do we produce the last row? Answer: we need to repeat the value, n times, in a list. Well, that's easy enough.

  6. Do we need to wrap the local row? Answer: Yes, because we want to append it as a single item to the recursive result - not concatenate all its elements.

Okay, let's re-examine the base case. Can we properly handle n == 0? Yes, and it makes perfect sense as a request, so we should handle it. What does our triangle look like with no rows in it? Well, it's still a list of rows, but it doesn't have any rows in it. So that's just []. And we can still append the first row to that, and proceed recursively. Great.

Let's put it all together:

if n == 0:
    return []
else:
    return my_function(n-1, value) + [[value] * n]

Looks like base_val isn't really useful any more. Oh well.

We can condense that a little further, with a ternary expression:

return [] if n == 0 else (my_function(n-1, value) + [[value] * n])
user_5236120
Related