recursion

readme.txt

一个纯函数，输出只取决于输入
使用最简单的情况举例，一个递归函数只存在一个递归调用
该递归调用讲函数分成三个部分，
1. 递归基 + 准备部分
2. 递归调用部分
3. 递归调用之后的部分

其中第一部分的 准备部分 可以影响递归调用的参数值
第三可以使用递归返回的值(写的时候可以认为这个值来自未来，或者有些更简单的情况，明显能感受到它就是从后往前在处理)

递：缩小问题规模 l[1:] , 也可以传递处理上一个数据和下一个数据所需要的中间状态，比如acc
归：利用未来的答案和当前的值来更新答案，l[0] + sum(xxx)

假设使用迭代解决sum问题
从汇编角度，设结果为result, 它只为result生成了一个位置，然后不断的更新这个位置的值

从递归的角度，每次调用函数都新生成了调用栈，获得答案可以
1. 直接使用最后一个栈的答案， 即尾递归 -> 即上面说的通过传递需要的中间状态，每次调用都更新这个中间状态，最后中间状态递归到底就是最终结果了
2. 用当前值 配合 未来结果 得到最终结果，这就是非尾递归了，即 l[0] + sum(l[1:])

理所当然的，用当前值 配合 未来的结果 这种写法十分优雅
然而它不是尾递归，不能直接优雅为最简单的循环

另外这种不需要传递中间状态的最简单递归还有一个显著的特点，可以很方便的从后往前递推，不需要附加中间状态
比如计算 [1,2,3]的和，可以先计算 [] 然后 0 + 3 然后 0 + 3 + 2 最后 0 + 3 + 2 + 1
但是前后有依赖的，就必须传递中间状态了，比如从[1,2,3] -> [1,3,6]
这个时候就必须传递acc了， 其实这个地方已经等同于迭代了
迭代的时候是每迭代一次更新result
传递acc实质是做相同的事情，只不过它是把它放到了函数调用参数的位置，最后递归也返回了函数参数

综上，递归写的爽是爽，写的越爽，越不好转换成迭代
因为尾递归基本就是把计算结果使用参数传递，我都得到中间计算结果了，何不直接写个循环呢

sum.py

def sum1(l):
    if not l:
        return 0
    return l[0] + sum1(l[1:])


def sum2(l):
    def inner(l, acc):
        if not l:
            return acc
        return inner(l[1:], acc + l[0])

    return inner(l, 0)

sum.sml

fun sum(l:int list) = 
        if null l then 0 else
            (hd l) + sum(tl l)

fun sum2(l:int list)=
        let
            fun inner(l: int list, acc : int) = 
                    if null l then acc
                    else inner(tl l, acc + hd l)
        in
            inner(l, 0)
        end

val a = sum([1,2,3]);
val b = sum([1,2,3]);