Scala 与尾递归

发表于 | 分类于 |

摘要：本文介绍递归和尾递归，以及转化方法。

参考文章

使用递归的方式去思考

Scala Learning(3): Tail Recursion定义

Scala尾递归优化

JVM原生不支持尾递归优化，但是Scala编译器支持

函数–尾递归

函数调用栈

我们首先需要理解什么是调用栈，我们首先思考一个最简单的问题，有两个函数 f(x) 和 g(x)，在 f(x) 内部调用了 g(x)：

1
2
3
4
5
f(x) {
	// do something
	n = g(x)
	// do something
}

当执行到 n = g(x) 时，在计算机内部需要将当前 f(x) 的信息保存到堆栈，然后开始执行 g(x)。因为当 g(x) 结束的时候，程序需要能够恢复现场，继续执行 f(x) 的后续步骤。这个保存的信息就是函数的调用栈。

如果我们不用递归，那么调用栈的深度实际完全由认为控制，取决于调用多深的函数。

尾调用

理解了函数调用栈，我们就可以来理解其中的一种特殊的函数调用栈，尾调用。为什么他特殊呢？ 因为函数调用处于尾部，比如上面的例子，如果是尾调用，就应该是如下形式：

1
2
3
4
5
f(x) {
	// do something
	n = g(x)
	// do nothing
}

那么为什么在尾部就特殊，我们再次回顾前面提到的函数调用栈的目的，保留当前函数执行的现场，然后在函数调用完成后恢复现场。但是如果一个函数在尾部，那么也就没有必要恢复现场，因为当前函数没有后续的工作了。正因为这个特性，尾调用可以复用堆栈。这个特性也能帮助递归调用降低空间复杂度。

尾递归

理解了尾调用，对于尾递归很好理解，就是所有的递归调用都为尾调用，这样的递归成为尾递归。

优化

通过一个例子，我们看看如何将非尾递归转化为尾递归

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

上面这个递归程序不是尾递归，因为在递归调用 factorial 之后，又对其结果进行了其他操作：乘以 n。那么我们能不能将其转化为尾递归呢？

下面代码就是尾递归版本，这里 Scala 语言特别增加了一个注释 @tailrec，该注释可以确保程序员写出的程序是正确的尾递归程序，如果由于疏忽大意，写出的不是一个尾递归程序，则编译器会报告一个编译错误，提醒程序员修改自己的代码。

1
2
3
4
5
6
7
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) 
}

尾递归转化方法

改写成尾递归版本的关键：
尾递归版本最重要的就是找到合适的累加器，该累加器可以保留最后一次递归调用留在堆栈中的数据，积累之前调用的结果，这样堆栈数据就可以被丢弃，当前的函数栈可以被重复利用。
在这个例子中，变量acc就是累加器，每次递归调用都会更新该变量，直到递归边界条件满足时返回该值。

思考

下面我们通过两种递归的执行过程来思考其区别，我们可以看到后者的关键在于，将所有的环境参数全部传入了递归函数中，这样递归过程不需要环境变量，就不需要存储堆栈。所以我们转化的关键在于找到这样一个能够接受其环境参数的尾调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
f(n)
f(5) = 5 * f(4) 
	 = 5 * 4 * f(3)
	 = 5 * 4 * 3 * f(2)
	 = 5 * 4 * 3 * 2 * f(1)
	 = 5 * 4 * 3 * 2 * 1 * f(0)
	 = 5 * 4 * 3 * 2 * 1 * 1
	 
t(acc,n)
我们acc 初始值为1,
t(1,5)  = t(1 * 5, 4)
		= t(1 * 5 * 4, 3)
		= t(1 * 5 * 4 * 3, 2)
		= t(1 * 5 * 4 * 3 * 2, 1)
		= t(1 * 5 * 4 * 3 * 2 * 1, 0)
		= 1 * 5 * 4 * 3 * 2 * 1

假设我们现在又递归函数 f(n1,n2..nk) 包含有若干个参数，同时当前递归函数中，依赖于 [m1,m2,...mk]，并产生结果 r。那么我们是否可以找到一个 t(r,[m1,m2,...mk], n1,n2..nk) 函数能够实现相同的计算过程，并产生结果r。
如果能找到，就说明我们能够成功的转化为尾递归。

其他方法

这里引用该文章针对 JS 的改写方法说明：

尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数。比如上面的例子，阶乘函数 factorial 需要用到一个中间变量 total ，那就把这个中间变量改写成函数的参数。这样做的缺点就是不太直观，第一眼很难看出来，为什么计算5的阶乘，需要传入两个参数5和1？

两个方法可以解决这个问题。方法一是在尾递归函数之外，再提供一个正常形式的函数。

1
2
3
4
5
6
7
8
9
10
function tailFactorial(n, total) {
  if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

function factorial(n) {
  return tailFactorial(n, 1);
}

factorial(5) // 120

上面代码通过一个正常形式的阶乘函数 factorial ，调用尾递归函数 tailFactorial ，看起来就正常多了。

函数式编程有一个概念，叫做柯里化（currying），意思是将多参数的函数转换成单参数的形式。这里也可以使用柯里化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function currying(fn, n) {
  return function (m) {
    return fn.call(this, m, n);
  };
}

function tailFactorial(n, total) {
  if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

const factorial = currying(tailFactorial, 1);

factorial(5) // 120

上面代码通过柯里化，将尾递归函数 tailFactorial 变为只接受1个参数的 factorial 。

第二种方法就简单多了，就是采用ES6的函数默认值。

1
2
3
4
5
6
function factorial(n, total = 1) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5) // 120

上面代码中，参数 total 有默认值1，所以调用时不用提供这个值。

总结一下，递归本质上是一种循环操作。纯粹的函数式编程语言没有循环操作命令，所有的循环都用递归实现，这就是为什么尾递归对这些语言极其重要。对于其他支持”尾调用优化”的语言（比如Lua，ES6），只需要知道循环可以用递归代替，而一旦使用递归，就最好使用尾递归。