CODEWITHSUNDEEP
recursionschemeracketfibonacci
Pradit
Pradit

Reputation: 719

Fibonacci in Scheme

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

Upvotes: 8

Views: 28405

Answers (3)

Telemachus
Telemachus

Reputation: 19705

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.

Upvotes: 8

Will Ness
Will Ness

Reputation: 71065

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

Upvotes: 4

Michael Segal
Michael Segal

Reputation: 25

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

Upvotes: -1

Related Questions