[SOLVED] Pascal's Triangle via Recursion

We can define a recursive pascal using a helper function, pairs.

pascal will return [[Int]] (an array of arrays of Int). For example, pascal(3) would return

[ [1],
  [1, 1],
  [1, 2, 1] ]

OK, so I'll show you all the code up front, but then I'll step through and explain certain bits afterwards.

def pairs (xs):
  if 2 > len(xs):
    return []
  else:
    return [xs[0:2]] + pairs(xs[1:])

def pascal (n):
  def compute (prev):
    return [1] + [x + y for (x,y) in pairs(prev)] + [1]
  def aux (m, prev):
    if (m > n):
      return []
    else:
      return [prev] + aux(m + 1, compute(prev))
  return aux(1, [1])

[print(line) for line in pascal(5)]
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]

Explanation

What we really care about is the pascal function. Everything else we've written was born out of the way we write pascal, so I'll start by going over that.

A very common way to write recursive functions is to use an inner auxiliary function that keeps track of our computation's various states. We'll be using this technique as the basis of our pascal function.

def my_recursive_func (<parameters>):
  def aux (<state_parameters>):
    if (<base_condition>):
      return <base_value>
    else
      return aux(<updated_state>)
  return aux(<initial_state>)

We already know how to fill in some of this boilerplate for our pascal function:

parameters should just be n, an Integer, because we expect to call our function like pascal(3) or pascal(5), etc – no other arguments should be accepted
state_parameters – we only know two things right now: 1) we will need some value m that counts up to n, incrementing by 1 each time – and 2) some value that allows us to compute the next row; we'll call it prev since each pascal row is computed based on the previous row
base_condition – when m == n we know we've generated all the rows we need, this is when we want to stop recursing
base_value – this is the last value returned – not quite sure what that should be yet
updated_state – we will update m using m + 1 and we will update the rows presumably using some kind of array concatenation – not exactly sure until we write more code
initial_state – we will start m at 1 and the first row of pascal is [1]

OK, let's fill in what we have so far:

def pascal (n):
  def aux (m, prev):
    if (m > n):
      return ?
    else:
      return aux(m + 1, ?)
  return aux(1, [1])

We'd like to have pascal build our result something like this:

[[1]] + [[1, 1]] + [[1, 2, 1]] + [[1, 3, 3, 1]], ...]
# => [ [1], [1 ,1], [1, 2, 1], [1, 3, 3, 1], ... ]

So in order to write the base_value and updated state for prev, we need to consider this return type. We want to return [[Int]], which is a list, so the base_value can simply be the empty list, [].

That means in each step, we actually want to take [prev] and concatenate (+) it to the recursive result as well ...

[prev] + aux(m + 1, <next_row>)

We're getting really close now. Let's update pascal again to see what we have to finish up:

def pascal (n):
  def aux (m, prev):
    if (m > n):
      return []
    else:
      return [prev] + aux(m + 1, <next_row>)
  return aux(1, [1])

Ok, so here comes the hard part – calculating the next row, right? Well, it's not too bad actually.

# Given
[1,2,1]

# the next row is
[1, (1 + 2), (2 + 1), 1]

Or another example

# Given
[1, 4, 6, 4, 1]

# the next row is
[1, (1 + 4), (4 + 6), (6 + 4), (4 + 1), 1]

So the pattern is something like this: Create a new array starting with 1, then for each pair of numbers in the previous row, add the two numbers together and append each sum to the array, then finally append another 1. We might express that in Python like using a list comprehension like this:

[1] + [x + y for (x,y) in pairs(prev)] + [1]

Now we just need to figure out that pairs function. pairs should have the following contract:

pairs([])        => []
pairs([a])       => []
pairs([a,b])     => [[a,b]]
pairs([a,b,c])   => [[a,b],[b,c]]
pairs([a,b,c,d]) => [[a,b],[b,c],[c,d]]

Let's implement it now and verify that our implementation fulfills the contract. Note, I'm implementing this function outside of pascal, because it's a generic function and useful on its own. To compute pascal rows, we need to add pairs of numbers, but adding or how we get those pairs or numbers should not be left as a responsibility for the pascal function itself.

def pairs (xs):
  if 2 > len(xs):
    return []
  else:
    return [xs[0:2]] + pairs(xs[1:])

print(pairs([]))        # []
print(pairs([1]))       # []
print(pairs([1,2]))     # [[1,2]]
print(pairs([1,2,3]))   # [[1,2],[2,3]]
print(pairs([1,2,3,4])) # [[1,2],[2,3],[3,4]]

OK, that's getting us really close now. Let's update the pascal function again to see where we're at:

def pascal (n):
  def aux (m, prev):
    if (m > n):
      return []
    else:
      return [prev] + aux(m + 1, [1] + [x + y for (x,y) in pairs(prev)] + [1])
  return aux(1, [1])

Holy smokes! We're already done. That aux call with the inline computation of the next row looks a little busy though. Let's add another helper inside pascal called compute to clean things up. Now we're done!

def pascal (n):
  def compute (prev):
    return [1] + [x + y for (x,y) in pairs(prev)] + [1]
  def aux (m, prev):
    if (m > n):
      return []
    else:
      return [prev] + aux(m + 1, compute(prev))
  return aux(1, [1])

Being thorough

If you want that goofy text and prompts to display, you can write main something like below. This keeps all the I/O separate from our pascal and pairs functions. This separation of concerns and managing of side effects is important to consider early in your program, because it's difficult to reuse functions that do more than we want them to.

def main ():
  try:
    print("Pascal triangle generator")
    n = int(input("Pascal(x): x = "))
    if n < 1: raise
    [print(line) for line in pascal(n)]
  except:
    print("enter a non-zero positive integer")
    main()

# run program
main()

Go ahead and run pascal(300) or something for some impressive results.