SICP1.2.2 树形递归 与 线性迭代(斐波那契数)

(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))

 

树形递归:计算步骤 随输入 指数性 增长,空间 随输入 线性 增长.

 

(define (fib n) (fib-iter 1 0 n)) (define (fib-iter a b count) (if (= count 0) b (fib-iter (+ a b) a (- count 1))))

 

线性迭代:计算步骤 随输入 线性 增长,空间 随输入 线性 增长.

 

用java写出来看看到底有多厉害:

/** * Created by Ramble on 2017/11/22. */public class Fib { public static long digui(long n) { if (n==0) return 0; if (n==1) return 1; else { return digui(n-1)+digui(n-2); } } public static long diedai(long n) { return diedai_iter(1, 0, n); } public static long diedai_iter(long a, long b, long count) { if (count==0) return b; else { return diedai_iter(a+b, a, count-1); } } public static void main(String[] args) { long startTime = System.currentTimeMillis(); System.out.println(digui(50L));// System.out.println(diedai(50L)); long endTime = System.currentTimeMillis(); System.out.println("程序运行时间："+(endTime-startTime)+"ms"); }}在n为50的时候:

树形递归程序运行时间：70805ms

而线性迭代绝大部分时候都是0ms.

(Java里面函数名不允许 - 这个符号)

转载于:https://www.cnblogs.com/R4mble/p/7881244.html

相关资源：JAVA上百实例源码以及开源项目