递归

计算斐波那契数列第n项

https://www.zhihu.com/question/20761771/answer/20672305t

int fib_1(int n) {
    if (n <= 1) {
        return 1 ;
    }
    else {
        return fib_1(n - 1) + fib_1(n - 2) ;
    }
}

//一种更高效的递归实现(线形递归)
int fib_2(int n) {
    int fib_rec(int a , int b , int n) {
        if (n <= 1) {
            return 1 ;
        }
        else {
            return a + fib_rec(b , a + b , n - 1)
        }
    }
    return fib_rec(1 , 1 , n)
}

//迭代(循环)实现
int fib_3(int n) {
    int a = 1 , b = 1 ;
    for(int i = 0 ; i < n ; ++i) {
        int a_ = b , b_ = a + b ;
        a = a_ ;
        b = b_ ;
    }
    return a
}

//尾递归实现
int fib_4(int n) {
    int fib_iter(int a , int b , int n) {
        if (n == 0) {
            return a;
        }
        else {
            return fib_iter(b , a + b , n - 1) ;
        }
    }
    return fib_iter(1 , 1 , n) ;
}