Pascal triangle recursion python

I"ve been practicing recursion lately and composed this code to gain Pascal"s triangle recursively.

You watching: Pascal triangle recursion python

How would certainly you men boost it ?

I do not really prefer the reality that the recursion goes for n+1 actions.

def RecPascal(n, m=1, prev=<>): if m > n+1: return <> elif m == 1: return RecPascal(n, m+1 , <1>) else: rerotate + RecPascal(n, m+1, calculate(prev))def calculate(prev): res = <0>*(len(prev)+1) res<0>, res<-1> = 1, 1 for i in range(0,len(res)): if res == 0: res = prev + prev return resfor line in RecPascal(10): print(line)
python python-3.x recursion
Share
Improve this question
Follow
edited Nov 16 "18 at 2:45

*

200_success
141k2121 gold badges182182 silver badges462462 bronze badges
asked Nov 15 "18 at 21:40
*

d_darricd_darric
16311 silver badge77 bronze badges
$endgroup$
2
Add a comment |

2 Answers 2


Active Oldest Votes
2
$egingroup$
Comparable to your Water Jug solution, this is still not an excellent recursive algorithm/implementation. But we can still critic it, and also carry out advantageous feedearlier.

See more: Hg Wells" The Time Machine Book Review, Book Review

First, the default dispute m=1 is awkward, which leads to the odd if m > n+1: and also if m == 1: test conditions. Changing the default dispute to zero reduces this oddness:

def RecPascal(n, m=0, prev=<>): if m > n: rerotate <> elif m == 0: rerevolve RecPascal(n, m+1 , <1>) else: rerevolve + RecPascal(n, m+1, calculate(prev))The elif m == 0: situation appears to exist just to seed the algorithm with the initially row of Pascal"s Triangle. The default value prev=<> is never used the code; if only one parameter is offered, the second value"s default reasons return RecPascal(n, m+1, <1>) to be executed and prev is not offered. If you instead usage <1> as the default value, you have the right to eliminate the n+1-th recursive step.

def RecPascal(n, m=0, prev=<1>): if m A little bit of inspection will expose that this is (prefer the Water Jug solution) simply a loop disguised as recursion; it can be recreated without recursion as:

def RecPascal(n): triangle = <> row = <> for _ in range(n): row = calculate(row) triangle.append(row) return triangleIn the calculate(prev) helper attribute, you initialize res to a row of zeros, and then fill in the end values through 1:

res = <0>*(len(prev)+1) res<0>, res<-1> = 1, 1You can relocation this with initializing res via a row of ones:

res = <1> * (len(prev)+1)Of course, then you can not look for the res == 0 values to fill in, but we do not have to look, we understand the specific indices that require filling in:

for i in range(1, len(res)-1): res = prev + prevThis offers a a lot cleaner helper feature. We can also get rid of a -1 by making use of utilizing the len(prev) rather of len(res):

def calculate(prev): res = <1> * (len(prev)+1) for i in range(1, len(prev)): res = prev + prev rerotate resIf we wanted to be tricky, we might add a 0 to the end of prev, and also then add equivalent elements of two slices of the prev list together, and prepend a 1 to the beginning:

def calculate(prev): prev = prev + <0> rerevolve <1> + , prev<:-1>)>Which functions like this:

prev + <0> -> < 1, 3, 3, 1, 0 > prev<1:> -> < 3, 3, 1, 0 >+ prev<:-1> -> < 1, 3, 3, 1 >----------------------------- <1> + < 4, 6, 4, 1 >This provides the correct generation of the initially row: calculate(<>) --> <1>. If we added 0 to both the start and also earlier, we"d correctly calculate the 1"s at each finish (0+1 = 1, and 1+0 = 1) however would certainly have to seed the initially row through <1>.

Because calculate is a helper for RecPascal, and will not be used all over else, you have the right to "hide" it by relocating it inside of RecPascal, presented below with the different calculation (prepfinishing & appending 0"s, seeding initially row as <1>) method:

def RecPascal(n): def calculate(prev): prev = <0> + prev + <0> return , prev<:-1>)> triangle = <> row = <1> for _ in range(n): triangle.append(row) row = calculate(row) return triangle