八、Scala编程之递归思想

发表于2021-03-26更新于2022-06-05字数统计1k阅读时长7分

Scala编程之递归思想

文章目录

1. 函数式编程(递归思想)

Scala 是运行在 Java 虚拟机（Java Virtual Machine）之上，因此具有如下特点:

  1. 轻松实现和丰富的 Java 类库互联互通。
  2. 它既支持面向对象的编程方式，又支持函数式编程。
  3. 它写出的程序像动态语言一样简洁，但事实上它确是严格意义上的静态语言。
  4. Scala 就像一位武林中的集大成者，将过去几十年计算机语言发展历史中的精萃集于一身，化繁为简，为程序员们提供了一种新的选择。设计者马丁·奥得斯基 希望程序员们将编程作为简洁，高效，令人愉快的工作。同时也让程序员们进行关于编程思想的新的思考。

Scala提倡函数式编程(递归思想)

先说下编程范式:

  1. 在所有的编程范式中，面向对象编程（Object-Oriented Programming）无疑是最大的赢家。
  2. 但其实面向对象编程并不是一种严格意义上的编程范式，严格意义上的编程范式分为：命令式编程（Imperative Programming）、函数式编程（Functional Programming）和逻辑式编程（Logic Programming）。面向对象编程只是上述几种范式的一个交叉产物，更多的还是继承了命令式编程的基
    因。
  3. 在传统的语言设计中，只有命令式编程得到了强调，那就是程序员要告诉计算机应该怎么做。而递归则通过灵巧的函数定义，告诉计算机做什么。因此在使用命令式编程思维的程序中，是现在多数程序采用的编程方式，递归出镜的几率很少，而在函数式编程中，大家可以随处见到递归的方式。

2. 应用实例：递归时间测试

scala中循环不建议使用while和do…while,而建议使用递归。

案例：计算1-50的和

常规的解决方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package recur

import java.text.SimpleDateFormat
import java.util.Date

object T1 {

  def main(args: Array[String]): Unit = {
    //传统方法完成 1-50 的求和任务
    val now: Date = new Date()
    val dateFormat: SimpleDateFormat =
      new SimpleDateFormat("yyyy-MM-dd HH:mm:ss")
    val date = dateFormat.format(now)

    println("date=" + date) //输出时间
    var res = BigInt(0)
    var num = BigInt(1)
    var maxVal = BigInt(99999999l) //BigInt(99999999l)[测试效率大数]
    while (num <= maxVal) {
      res += num
      num += 1
    }
    //耗时18s
    println("res=" + res) //res=4999999950000000
    //再一次输出时间
    val now2: Date = new Date()
    val date2 = dateFormat.format(now2)
    println("date2=" + date2) //输出时间
  }
}

函数式编程的重要思想就是尽量不要产生额外的影响,上面的代码就不符合函数式编程的思想, 下面我们看看使用函数式编程方式来解决(Scala提倡的方式)
测试：看看递归的速度是否有影响?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package recur

import java.text.SimpleDateFormat
import java.util.Date

object T2 {

  def main(args: Array[String]): Unit = {
    // 递归的方式来解决
    //传统方法完成 1-50 的求和任务
    val now: Date = new Date()
    val dateFormat: SimpleDateFormat =
      new SimpleDateFormat("yyyy-MM-dd HH:mm:ss")
    val date = dateFormat.format(now)
    println("date=" + date) //输出时间

    def mx(num: BigInt, sum: BigInt): BigInt = {
      if (num <= 99999999l) return mx(num + 1, sum + num)
      else return sum
    }

    //测试
    var num = BigInt(1)
    var sum = BigInt(0)
    var res = mx(num,sum)
    //耗费16s
    println("res=" + res) //输出：res=4999999950000000

    //再一次输出时间
    val now2: Date = new Date()
    val date2 = dateFormat.format(now2)
    println("date2=" + date2) //输出时间
  }
}

3. 应用案例：最大值

求最大值

1
2
3
4
5
6
7
8
//大话java数据结构
def max(xs: List[Int]): Int = {
if (xs.isEmpty)
	throw new java.util.NoSuchElementException
if (xs.size == 1)
	xs.head
else if (xs.head > max(xs.tail)) xs.head else max(xs.tail)
}

4. 应用案例：翻转字符串

1
2
def reverse(xs: String): String =
	if (xs.length == 1) xs else reverse(xs.tail) + xs.head

5. 应用案例：求阶乘

1
2
def factorial(n: Int): Int =
	if (n == 0) 1 else n * factorial(n - 1)