Pascal's Triangle via Recursion

Question

Can someone tell me if my current code is even possible? I have to create Pascal's Triangle with an input without using any loops. I am bound to recursion.

I have spent 3 days on this, and this is the best output that I can come up with.

def pascal(curlvl,newlvl,tri):

  if curlvl == newlvl:
    return ""

  else:

    tri.append(tri[curlvl])

    print(tri)
    return pascal(curlvl+1,newlvl,tri)


def triLvl():
  msg = "Please enter the number of levels to generate:"

  triheight = int(input(msg))

  if triheight < 1:
    print("\n Sorry, the number MUST be positive\n Please try again.")
    return triLvl()

  else:
    return triheight



def main():

   triangle = [1]

   curlvl = 0

   print("Welcome to the Pascal's triangle generator.")

   usrTri = triLvl()
   print(triangle)
   pascal(curlvl,usrTri,triangle)



main()

Answer 1

We can define a recursive pascal using helper function, pairs

pascal will return [[Int]] (an Array of Arrays of Int) – eg, 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 thru and explain certain bits afterward

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])

What we'd like to do is is 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 pard – 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 tho. 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 re-use 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