Pascal's triangle in python without using any loops

Question

So I'm trying to implement a pascal's triangle that produces the following in python:

pascal_triangle(5) prints:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

The problem is I'm trying to do it without using any type of loops but can't figure out how to do that. Any help would be appreciated. Than you.

This is what I have so far:

   def factorial(x):
            if x == 0:
                    return 1
            else: 
                    x * factorial(x - 1)

    def pascal_triangle(n):`

UPDATED:

print_pascal_line(r):
    if r == 0:
        return 1
    else:
        R = print_pascal_line(r-1)
        return 1 +

Answer 1

A simpler recursive solution that uses math to construct the triangle without any hidden loops:

def pascal(n, row=0):

    def pascal_row(numerator, denominator=1, number=1):
        if numerator > 0:
            number = number * numerator // denominator
            return [number, *pascal_row(numerator - 1, denominator + 1, number)]

        return []

    if row < n:
        return [[1, *pascal_row(row)], *pascal(n, row + 1)]

    return []

print(*pascal(10), sep='\n')

OUTPUT

% python3 test.py
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
%

Answer 2

First create a function that prints the Nth line of the pascal triangle, and I advise you to use combinations instead of manually computing the values in each line using factorials, it would be much more efficient. Let's say this function is called print_pascal_line and receives an integer, the line number.

Then you just have:

def pascal_triangle(n):
    aux(0, n)

def aux(current_line, n):
    if current_line < n:
        print_pascal_line(current_line)
        aux(current_line + 1, n)

Or you can use default arguments to have this in one function only:

def pascal_triangle(n, current_line = 0):
    if current_line < n:
        print_pascal_line(current_line)
        pascal_triangle(n, current_line + 1)

Answer 3

I answered this question once before here. Follow the link for an explanation of how to design recursive functions like this one.

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

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

Above we create a new [1] singleton in three places; two of which are part of the compute loop. We should create it once and reuse it instead.

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

A final improvement I might suggest is to use a generator instead of returning all of the rows eagerly

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

Now you can compute the output lazily, as it is consumed. If you want it all at once however, you can use list.

list(pascal(5))
# [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

Answer 4

A pure recursive solution (without loop, without assignment, without external modules, only python function used is sum which can be avoided as well). This code can be easily translated to LISP family language.

def pascal_line(n):
    def nextline(thisline):
        if thisline == []:
            return []
        else:
            return [sum(thisline[:2])] + nextline(thisline[1:])
    if n == 1:
        return [1]
    elif n == 2:
        return [1, 1]
    else:
        return [1]+nextline(pascal_line(n-1))

def pascal_triangle(n):
    def printline(m):
        if m <= n:
            print(*pascal_line(m))
            printline(m+1)
    return printline(1)

pascal_triangle(6)
# output =>
# 1
# 1 1
# 1 2 1
# 1 3 3 1
# 1 4 6 4 1
# 1 5 10 10 5 1

Inner function nextline derives the next line (without leading 1) in pascal triangle based on current line recursively.

Function pascal_line derives the nth line in a pascal triangle, by calling nextline recursively with (n-1)th line (its own previous solution).

Function pascal_triangle prints out lines in pascal triangle by calling pascal_line recursively.

Three recursive functions all together nicely illustrated the typical divide and conquer nature of recursive approach.

Answer 5

Each element of Pascal's triangle is evaluated using the binomial coefficient. This value, often referred to as nCr, asks "given n items how many ways can you Choose r things?"

Take, for example, the items a, b, and c. How many ways can we create combinations of the following sizes?

0. There's only 1 way to choose 0 items: {}
1. There are 3 possible combinations: {a}, {b}, or {c}
2. Again, 3 ways: {a, b}, {a, c}, or {b, c}
3. Only {a, b, c}

And what would you know, that just so happens to be level 3* of Pascal's triangle: 1 3 3 1! As it turns out, we can use this on every level.

0: nCr(0, 0)
1: nCr(1, 0) nCr(1, 1)
2: nCr(2, 0) nCr(2, 1) nCr(2, 2)
3: nCr(3, 0) nCr(3, 1) nCr(3, 2) nCr(3, 3)
etc
etc

So, how can we code for this? Looking at this answer we get our nCr function

In [454]: import functools as ft

In [455]: import operator as op

In [456]: def nCr(n, r):
     ...:     r = min(r, n-r)
     ...:     numer = ft.reduce(op.mul, range(n, n - r, -1), 1)
     ...:     denom = ft.reduce(op.mul, range(1, r + 1), 1)
     ...:     return numer // denom
     ...:

Finally, let's make a recursive function to tie it all together.

In [457]: def pascal(n):
     ...:     if n >= 1:
     ...:         pascal(n - 1)
     ...:         print(' '.join(str(nCr(n - 1, r)) for r in range(n)))
     ...:

In [463]: pascal(5)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Technically, this is should be pascal(4) as Pascal's triangle is zero-indexed*, but I'm just going according to the OPs request. If we wanted to change this we would alter our pascal function to

In [468]: def pascal(n):
     ...:     if n >= 0:
     ...:         pascal(n - 1)
     ...:         print(' '.join(str(nCr(n, r)) for r in range(n + 1)))
     ...:

Answer 6

How about this?

def pascal_triangle(n, line=None):
    if n == 0: return
    if line is None: 
        line = [1]
    print(" ".join(map(str, line)))
    pascal_line(line)
    pascal_triangle(n-1, line)

def pascal_line(line, i=0, add=0):
    if i >= len(line):
        line.append(add)
        return
    add, line[i] = line[i], line[i] + add
    pascal_line(line, i+1, add)