确认识递归.org

* 正确认识递归
** 可终止性证明
   如果N传负数的话，就死循环了。
sum(0) ->
    0.
sum(N) when N > 0->
    N + sum(N-1).

    这也是上次玩家经验为什么能吃掉16G内存的原因，递归没法终止。

** 小心++
   A ++ B的实现是将List A甩到一个新分配的内存空间，然后将B接过去，所以主要操作时间复杂度就是甩A。也就是可以简单认为跟A长度有关。

rev([X | TheRest]) ->
    rev(TheRest) ++ [X];
rev([]) ->
    [].
    正确写法
tail_rev([X | TheRest], Acc) ->
    tail_rev(TheRest, [X | Acc]);
tail_rev([], Acc) ->
    Acc.

** 小心length
   length的复杂度是O(N)
loop(List) when length(List) > 0->
    do_sth;
loop(EmptyList) ->
    done.
    正确写法是用匹配
loop([H|T])->
    do_sth;
loop([]) ->
    done.

** 一维操作，返回结果是一个的
#+BEGIN_SRC erlang
sum(0) ->
    1;
sum(N) ->
    N+sum(N-1).

tail_sum(0, Product) ->
    Product;
tail_sum(N, Product) ->
    tail_sum(N-1, N+Product).

sum_benchmark(N) ->    
    test_misc:benchmark_timestamp("sum", fun() ->
                                       [sum(I) || I <- lists:seq(1, N)]
                               end),
    test_misc:benchmark_timestamp("tail_sum", fun() ->
                                       [tail_sum(I, 1) || I <- lists:seq(1, N)]
                               end),
    ok.
#+END_SRC

#+BEGIN_SRC
%% (p04_master_1@192.168.1.233)4> hipe_test:sum_benchmark(10000).
%% sum: 633497 ms
%% tail_sum: 417625 ms
#+END_SRC
    在伪递归的情况下，确实会快点，不需要栈的维护。

** 一维操作，返回结果是List
#+BEGIN_SRC erlang
tail_keystore(K, N, L, New) ->
    keystore(K, N, L, New, []).

keystore(Key, N, [H|T], New, Ans) when element(N, H) == Key ->
    lists:reverse([New|Ans]) ++ T;
keystore(Key, N, [H|T], New, Ans) ->
    keystore(Key, N, T, New, [H|Ans]);
keystore(_Key, _N, [], New, Ans) ->
    lists:reverse([New|Ans]).

keystore_benchmark(N) ->
    test_misc:benchmark_timestamp("keystore", fun() ->
                                                 lists:keystore(N+1, 1, [{I, I}|| I <- lists:seq(1,N)], {N+1, N+1})
                                              end),
    test_misc:benchmark_timestamp("tail_keystore", fun() ->
                                                      tail_keystore(N+1, 1, [{I, I}|| I <- lists:seq(1,N)], {N+1, N+1})
                                                   end),
    ok.
#+END_SRC

#+BEGIN_SRC
(search)`key': hipe_test:keystore_benchmark(1000).
keystore: 123 ms
tail_keystore: 104 ms
ok
(p04_master_1@192.168.1.233)9> hipe_test:keystore_benchmark(10000).
keystore: 1155 ms
tail_keystore: 1242 ms
#+END_SRC
   时间差不多，理论时间复杂度也是一样。
** 二维操作
#+BEGIN_SRC

fib(0) ->
    1;
fib(1) ->
    1;
fib(N) ->
    fib(N-1) + fib(N-2).

tail_fib(N) -> fib_iter(N, 1, 1).
fib_iter(0, Result, _Next) ->
    Result;
fib_iter(Iter, Result, Next) 
  when Iter > 0 ->
    fib_iter(Iter-1, Next, Result+Next).

fib_benchmark(N) ->
    test_misc:benchmark_timestamp("fib", fun() ->
                                                 fib(N)
                                         end),
    test_misc:benchmark_timestamp("tail_fib", fun() ->
                                                      tail_fib(N)
                                              end),
    ok.
#+END_SRC
   递归的时间消耗成O(2^N)，伪递归是O(N)。
#+BEGIN_SRC
(p04_master_1@192.168.1.233)1> hipe_test:fib_benchmark(10).
fib: 3 ms
tail_fib: 1 ms
ok
(p04_master_1@192.168.1.233)2> hipe_test:fib_benchmark(15).
fib: 28 ms
tail_fib: 1 ms
ok
(p04_master_1@192.168.1.233)3> hipe_test:fib_benchmark(17).
fib: 76 ms
tail_fib: 1 ms
ok
(p04_master_1@192.168.1.233)4> hipe_test:fib_benchmark(18).
fib: 112 ms
tail_fib: 1 ms
ok
(p04_master_1@192.168.1.233)5> hipe_test:fib_benchmark(20).
fib: 312 ms
tail_fib: 1 ms
ok
(p04_master_1@192.168.1.233)6> hipe_test:fib_benchmark(26).
fib: 5450 ms
tail_fib: 1 ms
ok
(p04_master_1@192.168.1.233)7> hipe_test:fib_benchmark(30).
fib: 36306 ms
tail_fib: 2 ms
ok
(p04_master_1@192.168.1.233)8> hipe_test:fib_benchmark(32).
fib: 98214 ms
tail_fib: 1 ms
ok
(p04_master_1@192.168.1.233)9> hipe_test:fib_benchmark(33).
fib: 158971 ms
tail_fib: 1 ms
ok
#+END_SRC
** 高维操作
   ABCD * 9 = DCBA.前段时间，weibo有家长吐槽现在的小学数学题越来越难，我就手贱写了程序暴力枚举看看。

#+BEGIN_SRC
abcd() ->
    abcd(1,0,0,0).
abcd(A, B, C, D) 
  when (A*1000+B*100*C*10+D)*9 =:= D*1000+C*100*B*10+A->
    {A,B,C,D};
abcd(A, B, C, D) when A=<9, B=<9, C=<9, D=<9->
    abcd(A+1, B, C, D),
    abcd(A, B+1, C, D),
    abcd(A, B, C+1, D),
    abcd(A, B, C, D+1);
abcd(_,_,_,_) ->
    ok.
1 1 1 1

1 2 1 1
2

2 1 1 1
  2
ok_abcd() ->
    [{A, B, C, D} || A <- lists:seq(0,9),
                    B <- lists:seq(0,9),
                    C <- lists:seq(0,9),
                    D <- lists:seq(0,9),
                    9*(A*1000+B*100+C*10+D) =:= D*1000+C*100+B*10+A].
#+END_SRC
   两者算法复杂度实际是不一样，这个函数没法在机子跑完。
。
** 何时伪递归
   loop函数，比如我们服务器的等待消息的状态管理，如果不是伪递归的话，随着时间的增长，内存就慢慢的上去了。

   Tail递归和递归的区别就是栈的创建和复用。

   一般有性能差距就要尝试分析两者算法实现复杂度是不是不一样以及对栈的使用区别。

   一维操作的话，返回List的话，算法复杂度一样情况下，伪递归和递归是没太大区别，因为需要用reverse；返回单个的话，伪递归会优点。

   多维操作，递归就要小心了。

** 引用The Eight Myths of Erlang Performance
2.3 谬论：尾递归函数比递归函数快很多
据说，递归函数在栈上留下了很多无用的项（term，在erlang中代表所有数据类型，这里翻译成项，下同），垃圾回收机制必须拷贝这些无用的项，而尾递归会马上释放这些项。
在R7B之前这是正确的，在R7B中，编译器开始重新生成代码，把从来不会被用到的项的引用重写成空列表，这样垃圾回器收器就再也不必保存无用的值了。
就算进行了优化，在绝大多数时间里，尾递归函数比递归函数要快，why？
首先，必须弄清楚每次递归调用消耗了多少栈空间。大多数情况下，递归函数每次递归需要的栈空间比尾递归函数每次递归所分配的堆空间要多。因为更多的内存消耗，垃圾回收器要更频繁的回收，这会增加对栈的操作。
在R12B以及后续版本中，进行了优化，大多数情况下会减少递归调用需要的栈空间，所以，列表递归的函数和一个尾递归+lists:reverse/1恰好需要相同的内存。lists:map/2，lists:filter/2，列表解析，以及其他递归函数和他们的尾递归版本相比，消耗同样数量内存。（靖阳:注意这里指的是列表的递归）。
那么到底谁快？
要根据实际情况。在Solaris/Sparc上，递归函数似乎稍微快些，甚至是有很多元素的列表。而在X86架构中，尾递归要快30%。
所以现在更像是根据个人口味来选择。如果你真的需要速度至上，必须测试。你再也不能完全肯定，尾递归列表函数在所有的环境中都是最快的。
注意：一个尾递归函数，如果不需要再最后进行倒转，显然比一个递归函数要快，因为尾递归函数不需要构造任何项（例如，对列表中所有整数求和的函数）。