Fibonacci in Scheme

Question

I am trying to understand recursion in Scheme and I have a hard time doing the dry run for it, for example a simple Fibonacci number problem.

Could someone break down the steps in which the additions take place, for me?

(define (fib n)
  (if (<= n 2)
      1
      (+ (fib (- n 1)) (fib (- n 2)))))

Solution 1

If you're using Racket, as your tags indicate, then you have a built-in stepper.

Enter the program into DrRacket, and click Step in the top-right menu:

Then a stepper window will open up. Click Step over and over, and you can walk through the execution of the program.

If you want the number of steps to be a bit more manageable, pick a number lower than 10 for the execution to trace.

Solution 2

In pseudocode, fib(n) = n <= 2 -> 1 ; else -> fib(n-1) + fib(n-2) => (1 1 2 3 5 ...).

For example, fib(5) is reduced as:

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + fib(3)
((fib(2) + fib(1)) + fib(2)) + fib(3)
((1 + 1) + fib(2)) + fib(3)
(2 + fib(2)) + fib(3)
(2 + 1) + fib(3)
3 + fib(3)
3 + (fib(2) + fib(1))
3 + (1 + 1)
3 + 2
5