Project Euler 2

Implementaremos 2 soluções para o problema de nº 2 do Project Euler:

Estamos implementando uma solução através do uso de recursividade (RecursiveFibonacciEvenSum) e outra utilizando um loop (FibonacciEvenSum).

Function RecursiveFibonacciEvenSum([Long]$pre, [Long]$cur, [Long]$evenSum) {
    If ($cur -gt 4000000) { Return $evenSum}
    If ($cur %2 -eq 0) { $evenSum = $evenSum + $cur }
    [Long]$tmp = $pre + $cur
    $pre = $cur
    $cur = $tmp
    RecursiveFibonacciEvenSum $pre $cur $evenSum
}
 
Function FibonacciEvenSum([Long]$pre, [Long]$cur) {
    [Long]$tmp = 0
    [Long]$evenSum = 0
 
    While($tmp -lt 4000000) {
        $tmp = $pre + $cur
        If ($tmp % 2 -eq 0) { $evenSum = $evenSum + $tmp }
        $pre = $cur
        $cur = $tmp
    }
    Return $evenSum
}
 
Clear-Host
$time = New-Object System.Diagnostics.Stopwatch
$time.Start()
RecursiveFibonacciEvenSum 1 1 0
$time.Stop()
$ts = $time.Elapsed
Write-Host "Tempo calculado com Recursividade:"
Write-Host $ts.Seconds "segundos e" $ts.Milliseconds "milisegundos"
 
$time2 = New-Object System.Diagnostics.Stopwatch
$time2.Start()
FibonacciEvenSum 1 1
$time2.Stop()
$ts2 = $time2.Elapsed
Write-Host "Tempo calculado com Loop:"
Write-Host $ts2.Seconds "segundos e" $ts2.Milliseconds "milisegundos"

Calculamos a soma dos números pares na Série de Fibonacci, obtendo 4613732 como resultado. Com relação ao tempo gasto, observamos que a implementação através de loop teve melhor desempenho do que a solução que utiliza recursividade.

4613732
Tempo calculado com Recursividade:
0 segundos e 157 milisegundos

4613732
Tempo calculado com Loop:
0 segundos e 28 milisegundos