SICP习题 1.11 (一个函数的递归与迭代)

递归:

(define (f n) (if (< n 3) n (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

(f 3)

 

迭代:

(define (f n) (if (< n 3) n (f-iter 0 1 2 n) ))

(define (f-iter a b c n) ( if (= a (- n 1)) (+ a (* 2 b) (* 3 c)) ( f-iter (+ a 1) a b n) ) )

(f 3)

以上为错误版,传的是函数值而不是下标.搞混了

 

(define (f n) (f-iter 2 1 0 0 n))

(define (f-iter a b c i n) (if (= i n) c (f-iter (+ a (* 2 b) (* 3 c)) a b (+ i 1) n)))

(f 4)

 

 

 

还是用java来跑一跑:

package diegui;/** * Created by Ramble on 2017/11/23. */public class Func { public static long digui(long n) { if (n<3) { return n; } else { return digui(n-1) + 2 * digui(n-2) + 3 * digui(n-3); } } public static long diedai(long n) { return diedai_iter(2, 1, 0, 0, n); } private static long diedai_iter(long a, long b, long c, long i, long n) { if (i==n) { return c; } else { return diedai_iter(a + 2*b + 3*c, a, b, i+1, n); } } public static void main(String[] args) { long startTime = System.currentTimeMillis(); // System.out.println(digui(37)); //35: 634170606 程序运行时间: 2001ms //37: 26106855398260 程序运行时间: 5458ms System.out.println(diedai(8400)); //3210482350611447134 程序运行时间: 0ms// 1000 2961429411400171259// 程序运行时间: 0ms//5000// 1325422001847469286// 程序运行时间: 16ms// 10000// Exception in thread "main" java.lang.StackOverflowError long endTime = System.currentTimeMillis(); System.out.println("程序运行时间: " + (endTime-startTime)+"ms"); }}递归在37就不行了,迭代跑到8400,long都装不下的时候依旧0ms.太残暴了.默念:当我们考虑的是在层次结构性的数据上操作,而不是对数操作时,将会发现树形递归计算过程是一中自然的,威慑力强大的工具.

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

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