学习Java函数式编程(五)：函数式思维与尾递归

发表于 | 分类于 | 阅读次数:
字数统计: 1,239 | 阅读时长 ≈ 5

这篇文章介绍函数式编程概念和尾递归。

什么是函数式编程

首先要厘清一些概念。

  • 命令式 & 声明式：编程一般遵循两种范式，一种是“命令式”，一种是“声明式”。前者专注于“如何做”，它的指令和计算机底层词汇非常接近，比如赋值、条件分支以及循环；后者则强调“做什么”，制定规则给出目标，如何实现交给系统决定。面向对象编程和函数式编程分别具体实践了这两种范式；

  • 纯粹的、无副作用的：一个方法不修改宿主类的状态，也不修改其它对象的状态，使用return返回所有的计算结果；

  • 引用透明的：函数只要传递同样的参数值，总是返回同样的结果；

  • 纯粹的函数式编程和函数式编程：前者不存在任何副作用，后者存在副作用，但不被该函数的调用者感知，或调用者不在意这些副作用(因为对调用者完全没有影响)；

  • 被称为“函数式”的函数：只能修改本地变量，引用的对象都应该是不可修改的对象，不应抛出任何异常；

  • 局部函数式：对某一部分输入值，结果是未定义的(输入有范围)；

  • 没有可感知的副作用：不改变对调用者可见的变量、不进行I/O、不抛出异常；

  • 记忆化/缓存：属于引用透明的重要属性，目的是避免重复计算；

通过上面这些概念，我们很容易对函数式编程有一个初步的认识。

这里放上维基百科的定义：

函数式编程（英语：functional programming）或称函数程序设计，又称泛函编程，是一种编程典范，它将计算机运算视为数学上的函数计算，并且避免使用程序状态以及易变对象。函数编程语言最重要的基础是λ演算（lambda calculus）。而且λ演算的函数可以接受函数当作输入（引数）和输出（传出值）。

比起指令式编程，函数式编程更加强调程序执行的结果而非执行的过程，倡导利用若干简单的执行单元让计算结果不断渐进，逐层推导复杂的运算，而不是设计一个复杂的执行过程。

尾递归

纯粹的函数式编程语言不包含while和for这样的迭代器，因为诱导修改对象；而使用递归可以消除每步都需要更新的迭代变量，在函数式编程中，递归的使用相当普遍。

但是通过学习虚拟机后容易知道，方法的调用无非就是在虚拟机栈上创建新的栈帧，请看下面这种情形：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class StackDemo {
    public static void main(String[] args) {
        int n = 5;
        int num = add01(n);
        System.out.println(num);
    }
    static int add01(int x) {
        System.out.println("add01: " + x);
        return x == 1 ? 1 : 2 * add01(x - 1);
    }
}

上述代码输出结果为：

1
2
3
4
5
6
add01: 5
add01: 4
add01: 3
add01: 2
add01: 1
16

在add01方法中，return语句的三目运算如果执行到了2 * add01(x - 1)，就会再次调用add01(x - 1)，此时原本的方法并没有执行结束，局部变量表仍开辟着内存，如此递归调用将导致不菲的开销，很容易造成StackOverflowError异常，从输出结果也可以看出，每次递归调用方法都执行了打印语句。

一种解决上述问题的方式是：方法采用尾递归，然后进行尾递归优化。

在原代码基础上添加add02方法：

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
public class StackDemo {
    public static void main(String[] args) {
        int n = 5;
        int num = add01(n);
        System.out.println(num);
        int num02 = add02(n);
        System.out.println(num02);
    }
    static int add01(int x) {
        System.out.println("add01: " + x);
        return x == 1 ? 1 : 2 * add01(x - 1);
    }
    private static int add0(int acc, int x) {
        System.out.println("add02: " + x);
        return x == 1 ? acc : add0(acc * 2, x - 1);
    }
    static int add02(int x) {
        return add0(1, x);
    }
}

以上代码输出：

1
2
3
4
5
6
7
8
9
10
11
12
add01: 5
add01: 4
add01: 3
add01: 2
add01: 1
16
add02: 5
add02: 4
add02: 3
add02: 2
add02: 1
16

add02采用了尾递归的写法，同样得到了正确的结果。

如果本例进行了尾递归优化，本例的执行将变成如下的伪代码(参考Tail Call Optimization and Java的分析)：

1
2
3
4
5
6
7
8
call add02(5)
    call add0(1, 5)
    update variables with (2, 4)
    update variables with (4, 3)
    update variables with (8, 2)
    update variables with (16, 1)
    return 16
return 16

可见该优化是通过迭代的方式，将局部变量表中的数据替换掉，以此减少栈的开销。

遗憾的是Java不支持尾递归优化，但是《Java 8实战》一书还是提倡用Stream取代迭代，用递归替换迭代，作者认为大多数时候编程效率要比细微的执行时间差异更重要。

参考

Tail Call Optimization and Java

Scala是如何实现尾递归优化的？