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

Brain

Answer 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.

Cool

Answer 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

Fuchsia

Answer 3

This is a code that prints the fibonacci sequence members from 1 to n each in a new line. Importnat to note, it's using two very simple helper functions. Hope this helps.

;Prints to the screen all the member up to the nth member in the fibonaci sequence (define (fibo n)
 (let ((i 1))
  (if (= n 1)
      (display 1)
      (fiboHelp i n))))

;Helper function that presents Fibonaci sequence from bottom index i until upper index n
(define (fiboHelp i n)
  (if (= i n)
      (display(fiboMember i))
      (begin
        (display (fiboMember i))
        (newline)
        (fiboHelp (+ i 1)n)))) 

;Returns the nth member of the Fibonaci sequence
(define (fiboMember n)
  (if (<= n 2)
      (+ 1 0)
      (+ (fiboMember(- n 1))(fiboMember(- n 2)))))

Boice