Scheme Code Analysis for Space vs. Time

Question

I'm working my way through the online MIT lectures for the classic 6.001 course: The Structure and Interpretation of Computer Programs.

I'm trying to gain an understanding of analyzing code complexity in terms of memory usage vs. execution time. In the first few lectures, they present a solution in Scheme for the Fibonacci Series.

The solution they present in the videos is one that has the characteristic of growing in memory space with x (Linear Recursion performance), which presents a big problem with the Fibonacci Series. As you try to find a larger Fibonacci number, the space required for the recursion becomes huge.

They suggest trying to find a way to get Linear Iteration performance, where the memory space needed remains constant throughout the computation and doesn't depend on x.

My solution is below. My specific question is, what is the performance analysis of my Scheme code below, in terms of memory usage vs. execution time?

(define (fib x)

  (define (fib-helper target total current-index i-2 i-1)
     (if (> current-index target)
            (if (= target 1)
                0
                total)
            (fib-helper target
                        (+ i-2 i-1)
                        (+ current-index 1)
                        i-1
                        (+ i-2 i-1))))

  (fib-helper x 1 3 0 1))

Answer 1

Seeing your call to fib-helper is a proper tail call, this will run in constant space.

I cant help you with execution time though :)

Answer 2

Well, considering that (fib n) causes n-1 calls to fib-helper, your solution runs in linear time. fib-helper only calls itself once for each iteration, and each iteration is a tail call, so your program runs in constant space.

This means that a call to (fib 1000) should only take about ten times the CPU time of (fib 100) while taking up the same amount of memory.