fibonacci.C File Reference

Fibonacci number computation: Three implementation strategies compared. More...

#include <iostream>
#include <cstdlib>
#include <chrono>
#include <tclap/CmdLine.h>
#include <tpl_arrayStack.H>
#include <ah-errors.H>

Include dependency graph for fibonacci.C:

Go to the source code of this file.

Classes
struct	Activation_Record
	Activation record structure for stack-based Fibonacci. More...

Macros
#define	NUM(p)   ((p)->n)
	Accessor macros for top of stack (current activation record)
#define	F1(p)   ((p)->f1)
#define	RESULT(p)   ((p)->result)
#define	RETURN_POINT(p)   ((p)->return_point)

Functions
long long	fib_recursive (int n)
	Compute Fibonacci number recursively.
long long	fib_iterative (int n)
	Compute Fibonacci number iteratively.
long long	fib_stack (int n)
	Compute Fibonacci number using explicit stack management.
int	main (int argc, char *argv[])

Variables
constexpr char	P1 = 1
	Return point labels (simulating goto targets after recursive calls)
constexpr char	P2 = 2
	Return point after second recursive call fib(n-2)

Detailed Description

Fibonacci number computation: Three implementation strategies compared.

This example demonstrates three fundamentally different approaches to computing Fibonacci numbers, each illustrating important programming concepts and trade-offs. The Fibonacci sequence is one of the most famous sequences in mathematics and computer science, making it perfect for teaching algorithm design.

The Fibonacci Sequence

Defined recursively as:

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

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

Three Implementation Strategies

1. Recursive (fib_recursive)

Approach: Direct translation of mathematical definition

Code Structure:

if (n <= 1) return n;
return fib(n-1) + fib(n-2);

Complexity:

• Time: O(2^n) - exponential! (many redundant calculations)
• Space: O(n) - call stack depth

Pros:

• Simple, intuitive code
• Matches mathematical definition
• Easy to understand

Cons:

• Extremely slow for large n
• Redundant calculations (F(3) computed many times)
• Stack overflow risk for large n

Best for: Educational purposes, small n, understanding recursion

2. Iterative (fib_iterative)

Approach: Bottom-up computation using a loop

Code Structure:

int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
  int temp = a + b;
  a = b;
  b = temp;
}
return b;

Complexity:

• Time: O(n) - linear, optimal!
• Space: O(1) - constant, only two variables

Pros:

• Fast and efficient
• Minimal memory usage
• No stack overflow risk

Cons:

• Less intuitive than recursive version
• Doesn't match mathematical definition directly

Best for: Production code, large n, performance-critical applications

3. Stack-based with Activation Records (fib_stack)

Approach: Simulates recursive call stack explicitly using ArrayStack

Key Concept: Shows how recursion works internally

What It Demonstrates:

• Activation records: Stack frames storing local variables and return addresses
• Call stack management: How function calls are tracked
• Return point management: Continuation-style programming
• Compiler internals: How compilers transform recursion

Complexity:

• Time: O(n) - similar to iterative (no redundant work)
• Space: O(n) - explicit stack (like recursive, but controlled)

Educational Value:

• Understand recursion at a low level
• See how tail-call optimization could work
• Learn about continuation-passing style
• Understand compiler transformations

Best for: Learning how recursion works, understanding call stacks

Performance Comparison

Method	Time	Space	Redundant Work
Recursive	O(2^n)	O(n)	Yes (exponential)
Iterative	O(n)	O(1)	No
Stack-based	O(n)	O(n)	No

When to Use Each

• Recursive: Never in production (too slow), only for learning
• Iterative: Always in production (fastest, simplest)
• Stack-based: Educational purposes, understanding recursion

Advanced Optimizations

For even better performance, consider:

• Matrix exponentiation: O(log n) time using matrix powers
• Memoization: Cache computed values (O(n) time, O(n) space)
• Closed-form formula: Binet's formula (O(1) but floating-point precision issues)

Usage Examples

# Compute F(10) using all methods
fibonacci -n 10
 
# Compare performance (recursive will be slow!)
fibonacci -n 30
 
# Use specific method
fibonacci -n 20 -m iterative
fibonacci -n 15 -m stack

See also

fib.C Similar example with different implementation details

tpl_arrayStack.H Stack implementation used for stack-based version

Author

Leandro Rabindranath León

Definition in file fibonacci.C.

Macro Definition Documentation

F1

#define F1

(

p

)

((p)->f1)

Definition at line 277 of file fibonacci.C.

NUM

#define NUM

(

p

)

((p)->n)

Accessor macros for top of stack (current activation record)

Definition at line 276 of file fibonacci.C.

RESULT

#define RESULT

(

p

)

((p)->result)

Definition at line 278 of file fibonacci.C.

RETURN_POINT

#define RETURN_POINT

(

p

)

((p)->return_point)

Definition at line 279 of file fibonacci.C.

Function Documentation

fib_iterative()

long long fib_iterative

(

int

n

)

Compute Fibonacci number iteratively.

Bottom-up computation maintaining only the last two values.

Time complexity: O(n) - linear Space complexity: O(1) - constant

Parameters

n	The index of the Fibonacci number to compute

Returns

The n-th Fibonacci number

Definition at line 227 of file fibonacci.C.

References Aleph::maps().

Referenced by main().

fib_recursive()

long long fib_recursive

(

int

n

)

Compute Fibonacci number recursively.

Classic recursive definition: fib(0) = 0 fib(1) = 1 fib(n) = fib(n-1) + fib(n-2)

Time complexity: O(2^n) - exponential Space complexity: O(n) - call stack depth

Parameters

n	The index of the Fibonacci number to compute

Returns

The n-th Fibonacci number

Definition at line 202 of file fibonacci.C.

References fib_recursive().

Referenced by fib_recursive(), and main().

fib_stack()

long long fib_stack

(

int

n

)

Compute Fibonacci number using explicit stack management.

This implementation manually manages what the compiler does automatically for recursive calls:

1. Push a new activation record before each "recursive call"
2. Set up parameters in the new record
3. Record the return point (continuation)
4. Jump to the start of the function body
5. On "return", pop the record and jump to the saved return point

The flow simulates this recursive code:

long long fib(int n) {
  if (n <= 1) return (n <= 0) ? 0 : 1;  // Base case
  long long f1 = fib(n - 1);            // First recursive call (P1)
  long long f2 = fib(n - 2);            // Second recursive call (P2)
  return f1 + f2;
}

Time complexity: O(2^n) - same as recursive (we're simulating it exactly) Space complexity: O(n) - explicit stack instead of call stack

Parameters

n	The index of the Fibonacci number to compute

Returns

The n-th Fibonacci number

Definition at line 309 of file fibonacci.C.

References AH_ERROR, F1, Aleph::maps(), NUM, P1, P2, Aleph::ArrayStack< T >::pop(), Aleph::ArrayStack< T >::pushn(), RESULT, RETURN_POINT, Aleph::ArrayStack< T >::size(), and Aleph::ArrayStack< T >::top().

Referenced by main().

main()

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

Definition at line 398 of file fibonacci.C.

References fib_iterative(), fib_recursive(), fib_stack(), and Aleph::maps().

Variable Documentation

P1

constexpr char P1 = 1

constexpr

Return point labels (simulating goto targets after recursive calls)

Return point after first recursive call fib(n-1)

Definition at line 272 of file fibonacci.C.

Referenced by fib_stack().

P2

constexpr char P2 = 2

constexpr

Return point after second recursive call fib(n-2)

Definition at line 273 of file fibonacci.C.

Referenced by fib_stack().