/^[Rr]ex's Blog$/

(define (fibr n)
    (cond 
      ((= n 0) 0)
      ((= n 1) 1)
      (else
       (define (iter i n s1 s2)
         (cond 
           ((= i n) (+ s1 s2))
           ((< i n) (iter (+ i 1) n (+ s1 s2) s1))))
       (iter 2 n 1 0))))

题目：函数f 定义：如果  n < 3, 则 f(n)=n; 如果 n>=3 ，则 f(n) = f(n-1) + 2f(n-2) + 3f(n-3)。请使用递归和迭代计算f的过程。

程序:

#lang racket

#递归 


(define (f n)
  (cond ((< n 3) n)
        ((>= n 3) (+
                   (f (- n 1))
                   (* 2 (f (- n 2)))
                   (* 3 (f (- n 3)))))))
(newline)

(define (r func n)
  (printf "f(~a): ~a" n (func n))
  (newline))

(r f 0);0
(r f 1);1
(r f 2);2
(r f 3);4
(r f 4)
(r f 5)
(r f 10)
(r f 20)
(r f 30)

#迭代

(define (f-iter p2 p1 p0 index n)
  (let ((p3 (+ p2 p1 p1 p0 p0 p0)))
    (cond ((= index n) p3)
          ((< index n) (f-iter p3 p2 p1 (+ index 1) n)))))

(define (F n)
  (cond ((= 0 n) 0)
        ((= 1 n) 1)
        ((= 2 n) 2)
        (else (f-iter 2 1 0 3 n))))
  
(r F 0)
(r F 1)
(r F 2)
(r F 3)
(r F 4)
(r F 5)
(r F 10)
(r F 20) 
(r F 220)
(r F 10000)

结果:

f(0): 0
f(1): 1
f(2): 2
f(3): 4
f(4): 11
f(5): 25
f(10): 1892
f(20): 10771211
f(220): 13928702425972912434778793708927459826344702073964764586252602421117531233953024336
f(10000): 126882114367106230085249524897996848201577071358752344176384515130437059142543420415025939869809655761502993838142965408745467213384408810722039114213073321918169181348892973990650867875413482182340218332743085777395098529351186815795390283979619199793012212229652988313401048529120564866534145609667414754755473543622675674705503522747471746490735022730065161925091996119224389629741976396594387591422783607967367993795648069880478530411469250005367480383198002343787146642912026279998810672394894671220319803286484719482511764178070950280534302747217875299496470834210205308694093537637580053296144004439334657116516179393061272876540684764151397604128330564459039246070599654656742485453307190007117504472871362784300690043864755881876708188112488487405710904437806761960397272490001801216988676450191734559303064191230776769020969330832474285786736970757629583237911412691883183669176041386072510423349886487264077948042670618045664925265659911585392651800062823722191324622458134083487697826792532061052320562757044395852133650480410729278820144759635231213170429836987497639225265387774599582575531737059206461048193498430668114247515553133155034518628497725326725999878629553299014009978887060648245627717457977369273140965053370193689346412876846853126155956355087537444046701863285974573794604217637215433639213808959661839148524240201244033471973398384963785126285424264529641193165234338255225925022708936401709021712775682575941384049997253715104401679793780377062328978384487493417599402259219573765646124685001582087668128813204137436426451635165246116702368390758877455647644368193523752016782348585328766861427106002665650096745479270861639898554954577151112939725099802693229203680655733989908075890618318893663787032673188945719845254919382331042061269126990001516905356419683179070051210599475028410706960285383791128859411543711977305668655895401949908888968143098172700490359954231088364951714295240154749497881131070337907558229435338796071063741380309713368015162643994568831810589946227949317644494722743643416239538458322882850540658876898274791115999712853733163094400021513006139124770776660698804851923985707037632448543594243327075904243938727415700037002405078854264803988094502402945892693755437820348446120580751815511707558505055036822016774532089636513168063281493030612730784236680574838509442747602763391741013271122454155001111806610900964505026621623861650206551157634313718366839657411996139233264431869190126843569391313532607828516600928197553705711390545588682749567971703898296203922978637403233914515064033250424960433172916310895043897970918396688951098596962744246836016895580042480500489700763237238326700368066255716238273079553603461249617065415088620806993778699418575767045355464885396335879371192052620617018253963332206828418963049396742979040978030941332208269667742097865145434351171429472754593522415657293316957265139493504818688755100155316907866730356900964755968277384083979326757928437111863593244281380845619423007234439531076107944467594282864617901228014183818419550055401726692632810725683603425605228821470884453518917842793909351322051800642730801563956629800955292757464319000824912803406350978105745552028025441621753376813231255014708753064198957305065578355380353709438023423202372856437940626581063131156702953941900349967036467033042620248219548757232033710373539227744199580420884501837978502323071885584941682037994769250591367765241308766772068723324134801325074325544377150198437314408289440343651309713732830408523099082310444946587493740608053341079711256694192973308495790443988749053530358001525782416334401806083975837599434839674813391031607652741788296138286062277165852145305885440632719432465388464873947872429204300395495293857484751726497770632989369925358342900996875

SICP, 1.8, page17

#!/usr/bin/env racket
#lang racket

(define (root-iter guess x)
    (if (good guess x)
    	guess
	(root-iter (improved guess x) x)))

(define (good y x)
    (< (abs (- (* y y y) x)) 0.001))

(define (improved y x)
    (/ (+ (/ x y y) (+ y y)) 3))

(define (root x)
    (root-iter 1 x))

(root 30000.001)