fib.C File Reference

Fibonacci sequence: Three implementation strategies compared. More...

#include <cstdlib>
#include <iostream>
#include <tpl_arrayStack.H>

Include dependency graph for fib.C:

Go to the source code of this file.

Classes
struct	Item

Macros
#define	P0   0
#define	P1   1
#define	P2   2
#define	N   (stack.top().n)
#define	F1   (stack.top().f1)
#define	RESULT   (stack.top().result)
#define	RETURN_POINT   (stack.top().return_point)

Functions
int	fib_it (int n)
int	fib_rec (int n)
int	fib_st (int n)
int	main (int argc, char *argv[])

Detailed Description

Fibonacci sequence: Three implementation strategies compared.

This example demonstrates three different approaches to computing the Fibonacci sequence, each illustrating important programming concepts. The Fibonacci sequence is one of the most famous sequences in mathematics and provides excellent examples of different algorithmic approaches.

Fibonacci Sequence

Mathematical Definition

The Fibonacci sequence is defined recursively as:

• F(0) = 1
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n > 1

Sequence Values

Sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Mathematical Properties

• Golden ratio: Ratio F(n+1)/F(n) approaches φ ≈ 1.618
• Binet's formula: Closed-form expression exists
• Many applications: Nature, art, mathematics, computer science

Three Implementations

1. Iterative (<tt>fib_it</tt>)

Strategy: Use loop with two variables to track previous values

Algorithm:

fib_it(n):
  if n <= 1: return 1
  prev2 = 1, prev1 = 1
  for i = 2 to n:
    current = prev1 + prev2
    prev2 = prev1
    prev1 = current
  return current

Characteristics:

• Time: O(n) - linear time
• Space: O(1) - constant space
• Efficiency: Most efficient
• Best for: Production code, large n

2. Recursive (<tt>fib_rec</tt>)

Strategy: Direct translation of mathematical definition

Algorithm:

fib_rec(n):
  if n <= 1: return 1
  return fib_rec(n-1) + fib_rec(n-2)

Problem: Many redundant calculations!

Call tree for F(5):

         F(5)
        /    \
     F(4)    F(3)
    /   \    /  \
 F(3)  F(2) F(2) F(1)
... (many duplicate calls)

Characteristics:

• Time: O(2^n) - exponential! (terrible)
• Space: O(n) - call stack depth
• Redundancy: Calculates same values many times
• Best for: Educational purposes, small n only

3. Stack-based (<tt>fib_st</tt>)

Strategy: Simulate recursion using explicit stack

Algorithm:

fib_st(n):
  stack.push({n, return_point=P0})
  while stack not empty:
    item = stack.top()
    if item.n <= 1:
      item.result = 1
      stack.pop()
    else if item.return_point == P0:
      item.return_point = P1
      stack.push({n-1, return_point=P0})
    else if item.return_point == P1:
      item.f1 = result from previous call
      item.return_point = P2
      stack.push({n-2, return_point=P0})
    else:  // P2
      item.result = item.f1 + result from previous call
      stack.pop()

Characteristics:

• Time: O(n) - similar to iterative
• Space: O(n) - explicit stack
• Educational: Shows how recursion works internally
• Best for: Understanding recursion mechanics

Complexity Comparison

Implementation	Time	Space	Redundancy	Best For
Iterative	O(n)	O(1)	None	Production
Recursive	O(2^n)	O(n)	Massive	Education
Stack-based	O(n)	O(n)	None	Learning

Performance Example

Computing F(40):

• Iterative: ~40 operations, instant
• Recursive: ~2^40 operations, very slow!
• Stack-based: ~40 operations, fast

Educational Value

Concepts Demonstrated

This example teaches:

• Algorithm design: Different approaches to same problem
• Performance analysis: Time/space complexity comparison
• Recursion mechanics: How call stacks work internally
• Stack data structures: Using stacks to simulate recursion
• Optimization: Why naive recursion is inefficient

Learning Outcomes

After studying this example, you understand:

• Why naive recursion can be inefficient
• How to optimize recursive algorithms
• How recursion is implemented internally
• When to use iterative vs recursive approaches

Optimizations

Memoization (Not Shown)

Can optimize recursive version with memoization:

memo = {}
fib_memo(n):
  if n in memo: return memo[n]
  if n <= 1: return 1
  memo[n] = fib_memo(n-1) + fib_memo(n-2)
  return memo[n]

Time: O(n) - each value calculated once Space: O(n) - memoization table

Matrix Exponentiation (Advanced)

Can compute F(n) in O(log n) time using matrix exponentiation:

[F(n+1)]   [1 1]^n [1]
[F(n)  ] = [1 0]   [1]

Time: O(log n) - very fast!

Applications of Fibonacci

Nature

• Phyllotaxis: Leaf arrangement, flower petals
• Spiral patterns: Pine cones, sunflowers
• Growth patterns: Population growth models

Computer Science

• Algorithm analysis: Example of exponential recursion
• Dynamic programming: Classic DP example
• Golden ratio search: Optimization algorithms

Mathematics

• Number theory: Many interesting properties
• Combinatorics: Counting problems
• Graph theory: Fibonacci graphs

Usage

# Compute F(10) using all three methods
./fib 10
 
# Compare performance (recursive will be slow!)
./fib 20
 
# See exponential growth of recursive version
./fib 30  # Recursive takes much longer

Performance Warnings

⚠️ Warning: The recursive version is extremely slow for large n!

• F(30): Takes seconds
• F(40): Takes minutes
• F(50): Takes hours/days

Use iterative or stack-based for large values.

See also

fibonacci.C More comprehensive Fibonacci examples

tpl_arrayStack.H Stack implementation used for stack-based version

Author

Leandro Rabindranath León

Definition in file fib.C.

Macro Definition Documentation

F1

#define F1   (stack.top().f1)

Definition at line 295 of file fib.C.

N

#define N   (stack.top().n)

Definition at line 294 of file fib.C.

P0

#define P0   0

Definition at line 282 of file fib.C.

P1

#define P1   1

Definition at line 283 of file fib.C.

P2

#define P2   2

Definition at line 284 of file fib.C.

RESULT

#define RESULT   (stack.top().result)

Definition at line 296 of file fib.C.

RETURN_POINT

#define RETURN_POINT   (stack.top().return_point)

Definition at line 297 of file fib.C.

Function Documentation

fib_it()

int fib_it

(

int

n

)

Definition at line 258 of file fib.C.

References Aleph::divide_and_conquer_partition_dp().

Referenced by main().

fib_rec()

int fib_rec

(

int

n

)

Definition at line 271 of file fib.C.

References fib_rec().

Referenced by fib_rec(), and main().

fib_st()

int fib_st

(

int

n

)

Definition at line 299 of file fib.C.

References Aleph::divide_and_conquer_partition_dp(), Item::n, N, P1, P2, Aleph::ArrayStack< T >::pop(), Aleph::ArrayStack< T >::push(), RESULT, and Aleph::ArrayStack< T >::size().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 369 of file fib.C.

References Aleph::divide_and_conquer_partition_dp(), fib_it(), fib_rec(), and fib_st().