Here’s in python, imperatively, and then in functional style without the need for loops.

def pascal(n): | |

if n == 1: | |

return [ 1 ] | |

if n == 2: | |

return [ 1, 1 ] | |

prev = pascal(n–1) | |

results = [] | |

for i in range(n): | |

if i == 0: | |

continue | |

if i == n–1: | |

break | |

results.append(prev[i] + prev[i–1]) | |

return [1] + results + [1] | |

# functional style, no loops | |

def pascal_fp(n): | |

if n == 1: | |

return [ 1 ] | |

prev = pascal_fp(n–1) | |

return list(map(lambda x,y:x+y, [0] + prev, prev + [0])) |

Here’s in Haskell, I call it the gubatron’s method, explained in the comments.

Saw it by looking at a pattern while trying to solve it in paper, it just clicked.

Not sure if this is how other people code this solution.

— Gubatron's method | |

— n=3 [1, 2, 1] | |

— copy the list and append a 0 on the left of the first | |

— and append a 0 at the end of the second | |

— [0, 1, 2, 1] | |

— [1, 2, 1, 0] | |

— add them up! | |

— n=4 [1, 3, 3, 1] | |

— | |

— append 0s to both sides and add them up | |

— n=4 [1, 3, 3, 1] | |

— [0, 1, 3, 3, 1] | |

— [1, 3, 3, 1, 0] | |

— n=5 [1, 4, 6, 4, 1] | |

— and so on | |

— add two lists, for clarity | |

addLists :: Num c => [c] -> [c] -> [c] | |

addLists l1 l2 = zipWith (+) l1 l2 | |

pascal :: (Eq a1, Num a1, Num a2) => a1 -> [a2] | |

pascal 1 = [ 1 ] | |

pascal n = | |

let prev = pascal(n–1) | |

zero_prev = [0] ++ prev | |

prev_zero = prev ++ [0] | |

in | |

addLists zero_prev prev_zero | |

— [1,2,3] -> "1 2 3" | |

listToString = unwords. map show | |

— mapM_ -> map monadic so no weird IO errors are triggered | |

printTriangle n = mapM_ putStrLn (map listToString (map pascal [1..n])) | |

main = do | |

input <- getLine | |

printTriangle . (read :: String -> Int) $ input |