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

### 2 Responses to “One Step, Two Steps”

1. Rutger said

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