Pascal Triangle with recursion

Question

Ok, can someone tell me if my current code is possible. I have to create an input pascal triangle without using any loops. I owe recursion.

Ive spent 3 days on this and this is the best result I can come up with. his driving insane

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 triangle generator.") usrTri = triLvl() print(triangle) pascal(curlvl,usrTri,triangle) main() 

Answer 1

We can define a recursive pascal using the pairs helper function

pascal will return [[Int]] (an array of Int arrays) - for example, pascal(3) will return

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

OK, so I will show you all the code in front, but then I will take a step and explain some bits later

 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 [prev] 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

We really care about the pascal function - everything we wrote was born from the way we write pascal , so I'll start by looking at this.

A very common way to write recursive functions is to use an internal helper function that tracks our calculations in different states. We will use this technique as the basis of our pascal function pascal

 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 part of this template for our pascal function pascal

• parameters must be n , Integer, because we expect to call our function, for example pascal(3) or pascal(5) , etc., no other arguments should be accepted
• state_parameters - we know only two things right now: 1) we need some value of m , which is calculated to n , each time increasing by 1 - and 2) some value that allows us to calculate the next line; we will call it prev since each pascal line is calculated based on the previous line
• base_condition - when m == n we know that we have generated all the lines we need, this is when we want to stop recursion
• base_value is the last return value - not quite sure what else should be
• updated_state - we will update m using m + 1 , and we will update the lines, presumably using some kind of array concatenation - not entirely accurate until we write more code
• initial_state - we will start m at 1 , and the first pascal line will be [1]

Ok let's fill in what we still have

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

We would like 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, to write base_value and updated state for prev , we need to consider this type of return. We want to return [[Int]] , but since prev is [Int] , base_value must be [prev] , which has the correct type [[Int]]

This means that at every step we really want to take [prev] and combine ( + ) it with a recursive result ...

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

We are very close now, let's update pascal again to see that we have to complete

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

Ok, so here comes the hard pard - calculating the next line, right? Well, that is not so bad.

 # 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 template looks something like this: Create a new array starting with 1 , then for each pair of numbers in the previous line add two numbers together and add each sum to the array, and then add another 1 . We could express this in python, for example, using a list comprehension like this

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

Now we just need to find out what the pairs function is. pairs must 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 me implement it now and make sure that our implementation fulfills the contract. Please note: I implement this function outside of pascal because it is a general function and useful in itself. To calculate pascal strings, we need to add pairs of numbers, but adding or how we get these pairs or numbers should not be left as the responsibility of the pascal function.

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

It’s good that now we are really close. Update the pascal function to see where we are

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

Saints smoke! We are already done. This aux call with inline calculation of the next line seems a bit busy. Add another helper inside pascal called compute to clear things up. Now everything is ready!

 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 [prev] else: return [prev] + aux(m + 1, compute(prev) ) return aux(1, [1]) 

---

Be careful

If you want this dumb text and tooltips to appear, you can write main something like below. This allows us to separate all I / O from our pascal and pairs functions. It is important to consider this separation of problems and the management of side effects at an early stage of your program, because it is difficult to reuse functions that do more than we want.

 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 impressive results

Answer 2

I don't know, this is what you are looking for, but everything works fine:

 from operator import add def pascal(curlvl, newlvl, tri): if curlvl == newlvl: return "" elif curlvl == 0: tri.append(1) print (tri) return pascal(curlvl + 1, newlvl, tri) else: tmp = [1] rt = tri[:-1] rt.reverse() # print (map(add, rt, tri[:-1])) # In Python 3, map returns a generator. # Wrapping map in list makes this code compatible with # both Python 2 and 3 tt = list(map(add, rt, tri[:-1])) if (len(tt) > 0): tmp.extend(tt) tmp.append(1) tri = tmp 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 triangle generator.") usrTri = triLvl() print(triangle) pascal(curlvl, usrTri, triangle) main()