Fibonacci chart

Question

I'm trying to understand recursion in a Scheme, and it's hard for me to try it, for example, the simple Fibonacci problem.

Can someone break the steps in which the additions take place for me?

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

Answer 1

If you use Racket, as your tags show, you have a built-in stepper.

Enter the program in DrRacket and click Step in the upper right menu:

Then a step window will open. Click Step again and again, and you can see the program running.

If you want the number of steps to be a little more manageable, select a number less than 10 to track progress.

Answer 2

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

For example, fib(5) decreases 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 

Answer 3

This is code that prints elements of a fibonacci sequence from 1 to n each in a new line. Keep in mind that it uses 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 in)))) ;Helper function that presents Fibonaci sequence from bottom index i until upper index n (define (fiboHelp in) (if (= in) (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)))))