The first Fibonacci program I wrote was on my assembly language final in 1984 (PDP-11 assembly). During a DevOps interview I was asked to write an example of a Fibonacci program so I answered the question using PowerShell. The complete source code in text form can be found at the end of this post.
An example of a Fibonacci number being computed recursively (method Recursive) and sequentially (method Iterative):
The methods, Iterative and Recursive, are hidden. The publicly visible method, Compute, is used to compute the Fibonacci number:
The SequenceRecusrsive method is a hidden method that returns a Fibonacci sequence using a recursive computation:
The SequenceIterartive method is a hidden method that returns a Fibonacci sequence using an iterative computation:
The Sequence method is publicly visible and returns a Fibonacci sequence computed using either an iterative or recursive algorithm:
The test functions (below) verify the Fibonacci number computed and the Fibonacci sequence computed by comparing the value returned by the iterative implementation to the value returned by the recursive implementation:
Repeatedly invoking the functions TestFibonacci and TestFibonacci (see above) for values of 0, 1, 5, and 10 tests test the iterative against recursive implementations for multiple input values.
Appendix A: Source Code
Set-StrictMode -Version 3.0
class Fibonacci {
hidden static [int] Recursive([int] $n) {
if ($n -gt 1) {
return `
[Fibonacci]::Recursive($n - 1) +
[Fibonacci]::Recursive($n - 2)
}
else {
return $n
}
}
hidden static [int] Iterative([int] $n) {
if ($n -le 1) {
return $n
}
[int] $nMinus2 = 0
[int] $nMinus1 = 1
[int] $current = 0
for ([int] $i = 2; $i -le $n; $i++)
{
$current = $nMinus2 + $nMinus1
$nMinus2 = $nMinus1;
$nMinus1 = $current
}
return $current
}
static [int] Compute([int] $n, [bool] $isIterative) {
if ($isIterative) {
return [Fibonacci]::Iterative($n)
}
else {
return [Fibonacci]::Recursive($n)
}
}
hidden static [int[]] SequenceRecursive([int] $n) {
[Collections.Generic.List[int]] $sequence = `
[Collections.Generic.List[int]]::new()
if ($n -le 1) {
$sequence.Add($n)
return $sequence
}
for ([int] $i = 0; $i -le $n; $i++) {
$sequence.Add([Fibonacci]::Recursive($i))
}
return $sequence
}
hidden static [int[]] SequenceIterative([int] $n) {
[Collections.Generic.List[int]] $sequence = `
[Collections.Generic.List[int]]::new()
if ($n -le 1) {
$sequence.Add($n)
return $sequence
}
[int] $nMinus2 = 0
[int] $nMinus1 = 1
[int] $current = 0
for ([int] $i = 2; $i -le $n; $i++)
{
$sequence.Add($nMinus2)
$current = $nMinus2 + $nMinus1
$nMinus2 = $nMinus1;
$nMinus1 = $current
}
$sequence.Add($nMinus2)
$sequence.Add($current)
return $sequence
}
static [int[]] Sequence([int] $n, [bool] $isIterative) {
if ($isIterative) {
return [Fibonacci]::SequenceIterative($n)
}
else {
return [Fibonacci]::SequenceRecursive($n)
}
}
}
function TestFibonacci([int] $n) {
[int] $iterative = [Fibonacci]::Compute($n, $true)
[int] $recursive = [Fibonacci]::Compute($n, $false)
if ($iterative -ne $recursive) {
throw
"Fibonacci n = $n " +
"(iterative $iterative -ne recursive $recursive)"
}
return $iterative
}
function TestFibonacciSequence([int] $n) {
[string] $iterative = [Fibonacci]::Sequence($n, $true)
[string] $recursive = [Fibonacci]::Sequence($n, $false)
if ($iterative -ne $recursive) {
throw
"Fibonacci n = $n " +
"(iterative $iterative -ne recursive $recursive)"
}
return $iterative
}
TestFibonacci 0
TestFibonacciSequence 0
TestFibonacci 1
TestFibonacciSequence 1
TestFibonacci 5
TestFibonacciSequence 5
TestFibonacci 10
TestFibonacciSequence 10
No comments :
Post a Comment