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 can someone breakdown the steps in which the additions take place ?

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

回答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 http://f.cl.ly/items/341k1X2c44422e220T3I/Screen%20Shot%202013-02-01%20at%208.00.27%20PM.png

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 http://f.cl.ly/items/153A28283W263z421Y12/Screen%20Shot%202013-02-01%20at%208.02.51%20PM.png

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

回答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

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