One Step, Two Steps

August 18, 2017

This is a simple recursive process:

(define (f n)
  (if ( (f 0)
1
> (f 1)
1
> (f 2)
2
> (f 3)
3
> (f 4)
5
> (f 5)
8
> (f 6)
13

You may recognize this as the sequence of fibonacci numbers. It’s amazing to me how often the Fibonacci sequence appears; you might want to look at A000045 for lots more discussion. Here at Programming Praxis we’ve looked at fibonacci numbers several times in the past; this one is my favorite.

You can run the program at http://ideone.com/R46LUk.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
2 Comments »

2 Responses to “One Step, Two Steps”

  1. Rutger said
    August 21, 2017 at 11:20 AM

    Given you have reached step n, you could have gotten there in two ways:
    a) stepping to n-2 and doing a +2 step
    b) stepping to n-1 and going a +1 step

    so f(n) = f(n-2) + f(n-1), which reeks of Fibonacci with f(1) = 1 (take a +1 step), f(2) = 2 (take two +1 steps or one +2 step).

    For in implementation of Fibonacci I keep on ging this guy credits for his beautiful (although inefficient) Fib oneliner: http://paulhankin.github.io/Fibonacci/

    def fib(n):
    return (4 << n*(3+n)) // ((4 << 2*n) – (2 << n) – 1) & ((2 << n) – 1)

  2. bookofstevegraham said
    August 29, 2017 at 5:33 PM

    ZSG1 ;
    Q
    ;
    DO ;
    F I=1:1:10 W !,I," –> ",$$F^ZSG1(I,0,0)
    Q
    ;
    F(GOAL,SUBTOTAL,TALLY) ;
    S TALLY=$$G(GOAL,SUBTOTAL,TALLY,1)
    S TALLY=$$G(GOAL,SUBTOTAL,TALLY,2)
    Q TALLY
    ;
    G(GOAL,SUBTOTAL,TALLY,NUM) ;
    I SUBTOTAL+NUM>GOAL Q TALLY
    I SUBTOTAL+NUM=GOAL Q TALLY+1
    Q $$F(GOAL,SUBTOTAL+NUM,TALLY)

    1 –> 1
    2 –> 2
    3 –> 3
    4 –> 5
    5 –> 8
    6 –> 13
    7 –> 21
    8 –> 34
    9 –> 55
    10 –> 89

Leave a comment