CHAPTER 36. FIBONACCI NUMBERS CHAPTER 36. FIBONACCI NUMBERS
Chapter 36
Fibonacci numbers
Another widespread example used in programming textbooks is a recursive function that generates the Fibonacci numbers^1.
The sequence is very simple: each consecutive number is the sum of the previous two. The first two numbers are 1’s or 0, 1
and 1.
The sequence starts like this:
0 ; 1 ; 1 ; 2 ; 3 ; 5 ; 8 ; 13 ; 21 ; 34 ; 55 ; 89 ; 144 ; 233 ; 377 ; 610 ; 987 ; 1597 ; 2584 ; 4181 :::36.1 Example #1
The implementation is simple. This program generates the sequence until 21.
#include <stdio.h>
void fib (int a, int b, int limit)
{
printf ("%d\n", a+b);
if (a+b > limit)
return;
fib (b, a+b, limit);
};
int main()
{
printf ("0\n1\n1\n");
fib (1, 1, 20);
};
Listing 36.1: MSVC 2010 x86_a$ = 8 ; size = 4
_b$ = 12 ; size = 4
_limit$ = 16 ; size = 4
_fib PROC
push ebp
mov ebp, esp
mov eax, DWORD PTR _a$[ebp]
add eax, DWORD PTR _b$[ebp]
push eax
push OFFSET $SG2643
call DWORD PTR impprintf
add esp, 8
mov ecx, DWORD PTR _a$[ebp]
add ecx, DWORD PTR _b$[ebp]
cmp ecx, DWORD PTR _limit$[ebp]
jle SHORT $LN1@fib
jmp SHORT $LN2@fib
$LN1@fib:
mov edx, DWORD PTR _limit$[ebp]
push edx