The Pascal Triangle has some basic ground rules, all based on it's final/original structure:
1 The first column/row is 1
11 Where column = row is 1
121 The inside variables are a sum of the above row (row - 1), and neighbor to it's left (row - 1, column - 1)
1331
14641
Granted we are dealing with integers, we can formulate the above logic with a little Scala as:
def pascalLogic(r:Int, c:Int) =
// if first column/row or column = row
if (c == 0 || r == c) 1
// else sum of values
else pascalLogic(r-1, c) + pascalLogic(r-1, c+1)
To print out the pretty Pascal Triangle sans spaces, print the integer result for each message, and create line breaks at all instances where (r == c):
for (r <- 0 to c by 1) {
for (c <- 0 to r by 1)
print(pascalLogic(r, c) + " ")
println()
}
Combining the pieces :
def drawPascalTriangle(c:Int) { // curly brace creates closure/block/scope
for (r <- 0 to c by 1) {
for (c <- 0 to r by 1)
print(pascalLogic(r, c) + " ")
println()
def pascalLogic(r:Int, c:Int):Int =
if (c == 0 || r == c) 1
else pascalLogic(r-1, c) + pascalLogic(r-1, c-1)
}
}
drawPascalTriangle(12) COMMON RECURSIVE PATTERNS
- Linear (eg factorial)- Tree (eg Fibonacci, counting change)
- Primes and GCD
// factorial
def fac(x:Int, acc:Int):Int =
if (x == 0) 1
else if (x == 1) acc
else fac(x-1, acc * x)
// fibonacci
def fibo(n:Int):Int =
if (n==0) 0
else if (n==1) 1
else fibo(n-1) + fibo(n-2)
// counting change
def countChange(money:Int, coins:List[Int]):Int =
if (money == 0) 1 else if (money < 0 || coins.isEmpty) 0 else {
countChange(money - coins.head, coins) + countChange(money, coins.tail)
}
