Recursividade

Se tivermos um algoritmo para resolver um problema solucionando uma instância menor do mesmo problema, podemos usar funções recursivas. Reduz-se o problema até uma parte em que a recursividade cessa.

Quando se implementa recursividade, o exemplo clássico que nos vem à mente é o do cálculo do fatorial de um número. Se bem observarmos, o fatorial de um número é calculado multiplicando-o pelos números que o antecedem. Assim, fatorial de 6! = 6x5x4x3x2x1. E, por definição, o fatorial de 0! = 1.

Desse modo, é possível implementar facilmente uma função recursiva que calcule o fatorial de um número. Por exemplo:

Function fatorial([Int32]$num) {
    if ($num -eq 0) { return 1 }
    return $num * (fatorial($num-1))
}

Clear-Host
do {
    try {
        $numOk = $true
        [Int32]$num = Read-host `
        "Digite um número entre 0-100 para calcular o fatorial e pressione [ENTER]"
    }
    catch {$numOK = $false}
}
until (($num -ge 0 -and $num -le 100) -and $numOK)

Write-Host -NoNewline "O fatorial de $num é: "
fatorial($num)

Um exemplo de execução para o cálculo do fatorial de 7!

Digite um número entre 0-100 para calcular o fatorial e pressione [ENTER]: 7
O fatorial de 7 é: 5040

No post Invertendo Strings e Palíndromos, demonstramos uma maneira de implementar uma função que verifica se uma string é um palíndromo, ou seja, sua forma inversa tem escrita idêntica. É possível implementar uma função recursiva que verifica se uma string é palíndromo, mas fica apenas como exercício de programação, dado que a implementação no post anterior é bem mais simples.

Seguindo a ideia para funções recursivas de dividir um problema em instâncias menores, observamos que palavras são palíndromos quando a letra inicial e final são as mesmas. Assim, podemos usar esse algoritmo de testar se são iguais as letras inicial e final, removê-las e repetir a mesma lógica, até que não restem letras ou reste uma letra central. Se isso acontecer, a palavra é um palíndromo. Cada iteração seria uma chamada à função recursiva. O código poderia ser escrito assim:

Function trimFirstLast($pal) {
    $pal = $pal.TrimStart($pal[0])
    $pal = $pal.TrimEnd($pal[$pal.Length-1])
    return $pal
}

Function ehPalindromo([String]$pal) {
    if ($pal.Length -lt 2) { return $true }
    if ($pal[0] -ne $pal[$pal.Length-1]) { return $false }
    return ehPalindromo(trimFirstLast($pal))
}

$palavras = @("RELER","REVIVER","RADAR","ARARA","AMORA","SALAS",`
"ANILINA","MUSSUM","CASACA","MOTOR","OSSO","RIR","MIRIM","ROTOR")

Clear-Host

ForEach ($pal in $palavras) {
    Write-Host -NoNewLine "$pal é palíndromo? "
    ehPalindromo $pal
}

Com o seguinte resultado de execução:

RELER é palíndromo? True
REVIVER é palíndromo? True
RADAR é palíndromo? True
ARARA é palíndromo? True
AMORA é palíndromo? False
SALAS é palíndromo? True
ANILINA é palíndromo? True
MUSSUM é palíndromo? True
CASACA é palíndromo? False
MOTOR é palíndromo? False
OSSO é palíndromo? True
RIR é palíndromo? True
MIRIM é palíndromo? True
ROTOR é palíndromo? True

Referência: KHANACADEMY - Recursividade