Fibonacci in Scheme

23,315

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:

First step

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

Step by step

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
Share:
23,315
Pradit
Author by

Pradit

Computer science engineer

Updated on August 30, 2020

Comments

  • Pradit
    Pradit over 2 years

    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)))))