4.2 Recursividade

Fortran no Raspberry Pi

Função Fatorial no Code::Blocks no Raspberry Pi
Função Fatorial no Code::Blocks no Raspberry Pi

Toda vez que um procedimento (função ou sub-rotina) recursivo é chamado, é necessário alocar espaço em memória para armazenar as variáveis locais deste procedimento. Não é possível saber em tempo de compilação quantas vezes a chamada recursiva será executada e, portanto, não é possível alocar espaço estático em tempo de compilação para armazenar estas variáveis, o espaço deve ser alocado dinamicamente a cada chamada recursiva. A chamada recursiva pode ser direta, quando a função chama a si própria, e também indireta, quando a função chama uma outra função que a chama de volta.

Fatorial:

O fatorial de um número inteiro n, não negativo, é indicado por n! (lê-se “n fatorial”), e é definido pela relação:

n! = n⋅(n−1)⋅(n−2)⋅(n−3)...3⋅2⋅1, para m ≥ 2.

Sendo:

0! = 1
1! = 1

RECURSIVE FUNCTION fatorial(n) RESULT (f)
    ! Função para calcular o fatorial de um número.
    ! Recebe um número inteiro como argumento e retorna o fatorial.
    IMPLICIT NONE
    INTEGER, INTENT(IN) :: n
    INTEGER :: f
    IF (n .LT. 2) THEN
       f = 1
    ELSE
       f = n * fatorial(n-1)
    END IF
END FUNCTION fatorial
PROGRAM testa_fatorial
    ! Programa para ler um número e mostrar seu fatorial.
    IMPLICIT NONE
    INTEGER fatorial
    INTEGER numero
    PRINT *, 'Informe o número para calcular o fatorial:'
    READ *, numero
    PRINT *, 'Fatorial de ', numero, ' = ', fatorial(numero)
    STOP
END PROGRAM testa_fatorial

Makefile:

fatorial: fatorial.f90
	gfortran fatorial.f90 -o fatorial
clean:
	rm fatorial

Execução:

pi@raspberrypi:~/F/fatorial $ ./fatorial 
 Informe o número para calcular o fatorial:
0
 Fatorial de            0  =            1
pi@raspberrypi:~/F/fatorial $ ./fatorial 
 Informe o número para calcular o fatorial:
1     
 Fatorial de            1  =            1
pi@raspberrypi:~/F/fatorial $ ./fatorial
 Informe o número para calcular o fatorial:
2
 Fatorial de            2  =            2
pi@raspberrypi:~/F/fatorial $ ./fatorial
 Informe o número para calcular o fatorial:
5
 Fatorial de            5  =          120
pi@raspberrypi:~/F/fatorial $ ./fatorial
 Informe o número para calcular o fatorial:
10
 Fatorial de           10  =      3628800

Sequência de Fibonacci:

É definida pela fórmula Fₙ = Fₙ₋₁ + Fₙ₋₂, onde F₁ = 1.

RECURSIVE FUNCTION fibonacci(n) RESULT (termo)
    ! Função para calcular o termo n da sequência de Fibonacci.
    ! Recebe o número do termo como argumento e retorna o valor do termo.
    IMPLICIT NONE
    INTEGER, INTENT(IN) :: n
    INTEGER :: termo
    IF (n .LE. 1) THEN
       termo = 1
    ELSE
       termo = fibonacci(n-1) + fibonacci(n-2)
    END IF
END FUNCTION fibonacci
PROGRAM testa_fibonacci
    ! Programa para mostrar os valores dos primeiros
    ! termos da sequência de Fibonacci.
    IMPLICIT NONE
    INTEGER fibonacci, i, termo(23)
    DO i = 1, SIZE(termo)
       termo(i) = fibonacci(i)
    END DO
    PRINT '(5I8)', 0, 1, termo
    STOP
END PROGRAM testa_fibonacci

Makefile:

fibonacci: fibonacci.f90
	gfortran fibonacci.f90 -o fibonacci
clean:
	rm fibonacci

Execução:

pi@raspberrypi:~/F/fibonacci $ ./fibonacci 
       0       1       1       2       3
       5       8      13      21      34
      55      89     144     233     377
     610     987    1597    2584    4181
    6765   10946   17711   28657   46368

Referências: