I suppose there is a bit of something in there about using the right algorithm. But I can understand picking one that will take time for comparing speed. I'm not sure either is really representative of work you expect an editor to do, though. Curse of benchmarks.

Intuition: if you were to expand and flatten the recursive calls, you'd end up with something like

(+ 1 0 1 1 0 1 1 0 ... 1 0)

with exactly (fib n) 1s (base case (fib 1)), and no more than (fib n) 0s (base case (fib 0)).

Simple example:

     (fib 3)
     = (+ (fib 2) (fib 1))
     = (+ (+ (fib 1) (fib 0)) 1)
     = (+ (+ 1 0) 1)
     = (+ 1 0 1)

  With scm, using (trace proc):
 
 scm -f fib.scm
 
 call fib 9
    call fib 8
      call fib 7
        call fib 6
          call fib 5
          retn fib 5
          call fib 4
          retn fib 3
        retn fib 8
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
      retn fib 13
      call fib 6
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
      retn fib 8
    retn fib 21
    call fib 7
      call fib 6
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
      retn fib 8
      call fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
      retn fib 5
    retn fib 13
  retn fib 34
  call fib 8
    call fib 7
      call fib 6
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
      retn fib 8
      call fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
      retn fib 5
    retn fib 13
    call fib 6
      call fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
      retn fib 5
      call fib 4
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
        call fib 2
          call fib 1
          retn fib 1
          call fib 0
          retn fib 0
        retn fib 1
      retn fib 3
    retn fib 8
  retn fib 21
  55
 
 scm -f fib-iter.scm
 
 call fib-iter 1 0 10
    call fib-iter 1 1 9
      call fib-iter 2 1 8
        call fib-iter 3 2 7
          call fib-iter 5 3 6
          retn fib-iter 55
        retn fib-iter 55
      retn fib-iter 55
    retn fib-iter 55
  retn fib-iter 55
  55

That is, knowing all of these facts, it is still impressive how fast you can get (fib 1000000) using iteration and bignums.

Which is still not fast -- on my laptop, Python takes about 9s for fib(1000000). But compared to an exponentially-growing function, that's a blink of an eye.