一、使用递归的方式去思考
1、一个简单问题：对数列 xs 进行求和（不使用函数）
Python 循环解法：
def my_sum(xs):
sums = 0
for i in length(xs):
sums += xs[i]
return sums
Scala 递归解法：
//xs.head 返回列表的第一个元素（头元素）
//xs.tail 返回除头元素外剩余元素组成的列表
def my_sum(xs: List[Int]): Int =
if (xs.isEmpty) 0 else xs.head + my_sum(xs.tail)
-
使用 Scala 递归，只需一行，更简洁。
2、常见数据结构：反转字符串
Python 解法：
def reverse(xs):
return xs[::-1]
Scala 解法：
def reverse(xs: String): String =
if (xs.length==1) xs else reverse(xs.tail) + xs.head
-
使用 scala 递归，仍然只需一行。
3、经典数据结构：快速排序
Python 解法：
def quickSort(xs):
pivot = xs[0]
left = [elem for elem in xs if elem < pivot]
right = [elem for elem in xs if elem >= pivot]
return quickSort(left) + pivot + quickSort(right)
Scala 解法：
def quickSort(xs: List[Int]): List[Int] = {
if (xs.isEmpty) xs
else
quickSort(xs.filter(x=>x<xs.head)):::xs.head::quickSort(xs.filter(x=>x>xs.head))
}
4、尾递归
- 问题：相比循环，递归存在效率问题。因为每一次递归调用，都会分配一个新的函数栈，如果递归嵌套很深，容易出现栈溢出的问题。
- 解决方案：尾递归（在函数调用的最后一步，只调用该递归函数本身。此时无需记住其他的变量，当前的函数栈可以被重复使用）？
递归求阶乘（当 n 很大时，函数栈将很快被耗尽）
def factorial(n: Int): Int =
if (n == 0) 1 else n * factorial(n - 1)
尾递归求阶乘
def factorial(n: Int): Int = {
@tailrec //该注释用来确保程序员写出来的是正确的尾递归程序，如果不是，则编译器会报错
def loop(acc: Int, n: Int): Int =
if n == 0 acc else loop(n * acc, n - 1)
loop(1, n)
}
Note：在上面的尾递归程序中，在阶乘函数内部又定义了一个新的递归函数，该函数最后一步要么返回结果，要么定义该递归函数本身（对比前面的递归程序，可以发现它们非常相似，不同在于前面的递归程序最后一步不能直接返回结果，还需要计算）。新递归函数多出一个变量 acc，每次递归调用都会更新该变量，直到递归边界条件满足时返回该值，即为最后的计算结果。
5、零钱兑换问题
- 问题描述：假设某国的货币有若干面值，现给一张大面值的货币要兑换成零钱，问有多少种兑换方式？
Python 动态规划求解需要的最小硬币个素
def countChange(money, coins):
coins.sort()
dp = {0:0}
for i in range(1, money + 1):
dp[i] = money + 1
for j in coins:
if j <= i:
dp[i] = min(dp[i], dp[i-j] + 1)
if dp[money] == money + 1: #当最小硬币个数为最小值时，代表不存在硬币组合能构成此金额
return -1
else:
return dp[money]
Python 非递归解法：动态规划
def change(money, coins):
dp = [0] * (money + 1)
dp[0] = 1
for coin in coins:
for x in range(coin, money + 1):
dp[x] += dp[x - coin]
return dp[money]
Scala 递归解法
def countChange(money: Int, coins: List[Int]): Int = {
if (money == 0)
0
else if (coins.size == 0 || money < 0)
0
else
countChange(money, coins.tail) + countChange(money - coins.head, coins) //找零的方法数 = 不使用第一种硬币进行找零的方法数 + 使用第一种硬币进行找零的方法数
}
二、函数式编程
1、高阶函数与匿名函数
- 问题：练习题：求1-10的和、求1-10的平方和、求1-10的立方和、求1-10的阶乘和，如何编程求解？
使用高阶函数定义求和函数
def id(n: Int) = n
def cube(n: Int) = n * n * n //定义函数求立方
def square(n : Int) = n * n //定义函数求平方
def fact(n: Int): Int =
if (n == 0) 1 else n * fact(n - 1) //定义函数求阶乘
// 高阶函数
def sum(f: Int => Int, a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sum(f, a + 1, b) //定义求和函数
// 使用高阶函数定义求和函数
def sumInt(a: Int, b: Int): Int = sum(id, a, b)
def sumCube(a: Int, b: Int): Int = sum(cube, a, b)
def sumSquare(a: Int, b: Int): Int = sum(square, a, b)
def sumFact(a: Int, b: Int): Int = sum(fact, a, b)
- 思考：多数情况下，我们关心的是高阶函数，而不是作为参数传入的函数，所以为其单独定义一个函数是没有必要的。
在高阶函数中使用匿名函数
def fact(n: Int): Int =
if (n == 0) 1 else n * fact(n - 1)
// 高阶函数
def sum(f: Int => Int, a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sum(f, a + 1, b)
// 使用高阶函数重新定义求和函数
def sumCube(a: Int, b: Int): Int = sum(x => x * x * x, a, b) //使用匿名函数 x => x * x * x
def sumSquare(a: Int, b: Int): Int = sum(x => x * x, a, b) //使用匿名函数 x => x * x
def sumFact(a: Int, b: Int): Int = sum(fact, a, b)
def sumInt(a: Int, b: Int): Int = sum(x => x, a, b) //使用匿名函数 x => x
2、柯里化
Don’t Repeat Yourself !
- 问题：上面几个求和函数的上下限变量 a、b 被重复传来传去，如何解决？
返回函数的高阶函数
def fact(n: Int): Int =
if (n == 0) 1 else n * fact(n - 1)
// 高阶函数
def sum(f: Int => Int): (Int, Int) => Int = {
def sumF(a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sumF(a + 1, b)
sumF
}
// 使用高阶函数重新定义求和函数
def sumCube: Int = sum(x => x * x * x)
def sumSquare: Int = sum(x => x * x)
def sumFact: Int = sum(fact)
def sumInt: Int = sum(x => x)
- 再简化：
直接调用高阶函数
def fact(n: Int): Int =
if (n == 0) 1 else n * fact(n - 1)
// 高阶函数
def sum(f: Int => Int): (Int, Int) => Int = {
def sumF(a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sumF(a + 1, b)
sumF
}
// 这些函数没有必要了
//def sumCube: Int = sum(x => x * x * x)
//def sumSquare: Int = sum(x => x * x)
//def sumFact: Int = sum(fact)
//def sumInt: Int = sum(x => x)
// 直接调用高阶函数 !
sum(x => x * x * x) (1, 10) //=> sumCube(1, 10)
sum(x => x) (1, 10) //=> sumInt(1, 10)
sum(x => x * x) (1, 10) //=> sumSquare(1, 10)
sum(fact) (1, 10) //=> sumFact(1, 10)
- 上面的sum函数可以简写为：
高阶函数的语法糖
// 没使用语法糖的 sum 函数
def sum(f: Int => Int): (Int, Int): Int = {
def sumF(a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sumF(a + 1, b)
sumF
}
// 使用语法糖后的 sum 函数
def sum(f: Int => Int)(a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sum(f)(a + 1, b)