递归与尾递归

       一句话理解递归与尾递归

      递归就是普通涵数的调用，消耗资源

      尾递归就是最后一个调用自已，中间不需要处理数据，所以资源消耗层面很少。

      这就象迭代器的好处。

       编程很复杂，编程也很简单。简单的逻辑，通过代码组织，就可以变成复杂程序或者系统。以前学物理的时候，老师就说考试的物理题其过程是相当复杂的（简单的就没有必要考了）。解题方法众多，分解法即是一个行之有效的方式。复杂的过程经过分解，会变成简单的定理。如同螺丝，轮胎，玻璃都很简单，却能组合而成复杂的汽车。

编程也类似，核心哲学甚至简单得令人发指，其一是指针，其二是递归。深入理解者两个概念，很多复杂的系统或者设计，都会化繁为简，一目了然。

递归

递归，一个函数在内部调用自己，就是递归。递归在生活中也很常见，例如我们的眼睛，你看对方的眼睛，对方的眼睛里面有你，而那里面那个你又有她，无限循环。再比如，当你拿着一面镜子，对着另外一面镜子的时候，就会发现镜子之中有你手指的镜子，等等。

12903486_211n.jpg

尾递归

函数中可以调用自己成为递归，也可以在末尾调用别的函数。如果一个函数里的最后一个动作是一个函数调用的情形：即这个调用的返回值直接被当前函数返回的情形。这样的调用为尾调用。如果是尾调用自己，即为尾递归。

尾递归是一种形式, 这种形式表达出的概念可以被某些编译器优化. 尾递归的特殊形式决定了这种递归代码在执行过程中是可以不需要回溯的(通常的递归都是需要回溯的). 如果编译器针对尾递归形式的递归代码作了这种优化, 就可能把原本需要线性复杂度栈内存空间的执行过程用常数复杂度的空间完成.

尾递归通常用于实现以下重复的计算。而一般的语言却不支持尾递归，也就是并没有被优化。例如java, python。它们使用循环迭代来达到同样的效果。

阶乘计算

解释递归最常用的例子就是阶乘算法，下面使用 Python，Elixir，Scheme分别实现常用的递归算法。

class Factorial(object):
    @classmethod
    def recursion(cls, n):
        if n == 1:
            return 1
        return n * cls.recursion(n - 1)

Factorial.recursion(5)  # 输出 120

魔法书（SICP）中简单的演示了这个调用过程：

recursion(5)
5 * recursion(4)
5 * (4 * recursion(3))
5 * (4 * (3 * recursion(2)))
5 * (4 * (3 * (2 * recursion(1))))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

函数调用之后，会继续调用自身，并在栈里堆积内存。scheme的解法也很简单：

#lang scheme

(define (recursion n)
  (if (= n 1)
      1
      (* n (recursion (- n 1)))))

(recursion 5) ; 输出 120

同样，elixir也很容易实现：

defmodule Factorial do
    def recursion(n) when n == 1 do
        1
    end

    def recursion(n) do
        n * recursion(n-1)
    end
end

IO.puts Factorial.recursion(5) # 输出 120

上述是递归调用，并不是尾递归，如果使用尾递归，python代码如下：

class Factorial(object):

    @classmethod
    def tail_recursion(cls, n, acc=1):
        if n == 1:
            return acc
        return cls.tail_recursion(n - 1, n * acc)

Factorial.tail_recursion(5)

尾递归的调用过程大致是

tail_recursion(5, 1)
tail_recursion(4, 20)
tail_recursion(3, 60)
tail_recursion(2, 120)
tail_recursion(1, 120)
120

编译器会根据尾递归的方式，进行优化，使得递归调用的时候并不会向线性递归那样堆积内存。就和循环迭代的效果一样。这样也是函数式编程语言处理迭代的问题。

尾递归优化主要是对栈内存空间的优化, 这个优化是O(n)到O(1)的; 至于时间的优化, 其实是由于对空间的优化导致内存分配的工作减少所产生的, 是一个常数优化, 不会带来质的变化。

那么看看scheme的实现方式

(define (tail-recursion n acc)
  (if (= n 1)
      acc
      (tail-recursion (- n 1) (* n acc))))

(tail-recursion 5 1)

看了两个例子，尾递归还是很好理解。形式上盘的就是最后一个return的时候，是单纯的返回一个函数调用，还是返回函数计算。即

• 尾递归返回 return cls.tail_recursion(n - 1, n * acc) 只返回纯函数
• 普通递归返回 return n * cls.recursion(n - 1) 返回函数和别的表达式运算

函数式语言基本上都支持尾递归，用来做迭代功能，下面是elixir的例子

defmodule Factorial do
    def tail_recursion(n, acc) when n == 1 do
        acc
    end

    def tail_recursion(n, acc \\ 1) do
        tail_recursion(n-1, n * acc)
    end 
end

IO.puts Factorial.tail_recursion(5)

迭代与递归

函数式编程语言，通常没有其他语言所谓的循环关键字。需要迭代的时候，可以用递归实现。最初也比较难理解递归如何实现？实际上，处理循环的时候，都是通过循环因子控制循环条件，在循环体内进行处理计算。递归也可以这样做，递归的条件终止的条件可以用递归的参数设置。

下面演示给一个列表，遍历每一个列表的元素，并给每个元素的值翻倍。同样使用三种语言代表：

class Double(object):
    @classmethod
    def recursion(cls, lst):
        if not lst:
            return []
        else:
            head, tail = lst.pop(0), lst
            return [2 * head] + cls.recursion(lst)

    @classmethod
    def tail_recursion(cls, lst, new_lst=[]):
        if not lst:
            return new_lst
        else:
            head, tail = lst.pop(0), lst
            new_lst.append(2 * head)
            return cls.tail_recursion(tail, new_lst)


Double.recursion([1, 2, 3, 4, 5])
Double.tail_recursion([1, 2, 3, 4, 5])

Scheme

(define (recursion lst)
  (if (null? lst)
      `()
      (cons (* 2 (car lst)) (recursion (cdr lst)))))


(define (tail-recursion lst new-lst)
  (if (null? lst)
      new-lst
      (tail-recursion (cdr lst) (append new-lst (list (* 2 (car lst)))))))

(recursion (list 1 2 3 4 5))
(tail-recursion (list 1 2 3 4 5) `())

Elixir

defmodule Double do
    def recurssion([head|tail]) do
        [2 * head | recurssion(tail)]
    end

    def recurssion([]) do
        []
    end

    def tail_recursion([head|tail], new_list) do
        new_list = new_list ++ [2 * head]
        tail_recursion(tail, new_list)
    end

    def tail_recursion([], new_list) do
        new_list
    end
end

Double.recurssion([1, 2, 3, 4, 5])
Double.tail_recursion([1, 2, 3, 4, 5], [])

了解递归和尾递归之后，另外一个需要了解就是并不是每个语言都支持尾递归。上述的 python就不支持。Python使用尾递归，在数据量稍大的时候会溢出。此外，像 Scheme和Elixir这些语言则很好的支持。当需要在遍历的时候写逻辑，可以抽象出逻辑为一个个函数，更有利于代码的模块化和复用。

总结一下，普通递归过程是函数调用，涉及返回地址、函数参数、寄存器值等压栈等，而尾递归压栈操作并无必要，不会有中间结果需要缓存。通常是语言层面是否支持，编译器或解释器中进行优化。

 

作者：人世间
链接：http://www.jianshu.com/p/1f69cb4525ec
來源：简书

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。