Funções Recursivas - Recursividade em PHP

"Para entender recursividade, tem que saber recursividade".
Ao final deste tutorial de nossa apostila de PHP, vamos entender essa piadinha interna entre programadores.

Recomendo: Apostila de PHP para download

Função Recursiva

Uma função recursiva é nada mais nada menos que uma função que invoca...ela mesma.
Sim, isso mesmo, é uma função que chama ela mesma.

Obviamente se for só o código da função chamando ela mesmo, essa de dentro também vai chamar ela mesma, que vai chamar de novo ela mesma...e você criou um vírus, que vai consumir toda memória ram do computador (você pode upar esse código para seu servidor web e pegar seus amigos).

Para isso, deve necessariamente haver uma condição em que as funções para de se invocar.
É simplesmente um IF e ELSE.

Se atingir determinado valor de argumento, para de se invocar.
Senão, continua se invocando.

Vamos ver como calcular um somatório, um fatorial e a sequência de Fibonacci usando apenas recursividade.

Somatório com Recursão

Seja F(n) uma função que representa o somatório de um número n, ou seja, é a soma:
F(n) = 1 + 2 + 3 + 4 + ...+ (n-1) + n

Por exemplo:
F(4) = 1 + 2 + 3 + 4 = 10
F(5) = 1 + 2 + 3 + 4 + 5 = 15
...
Porém, note uma coisa:
F(5) = (1 + 2 + 3 + 4) + 5 = F(4) + 5

Ou seja:
F(n) = n + F(n-1)

Então vai funcionar assim:
Vamos criar uma função de somatorio() que chega se o argumento for 1, se for, retorna 1 e acabou o programa.

Se não for 1, retorna n + somatorio(n-1);

Veja como fica o código:
<html>
 <head>
  <title>Apostila PHP Progressivo</title>
 </head>
 <body>
 <form action="" method="get">
  Somatório de: <input type="number" name="number" /><br />
  <input type="submit" name="submit" value="Calcular" />
 </form> 
 <?php
  $numero = $_GET['number'];
  echo "O somatório de $numero é : ".somatorio($numero);
  
  function somatorio($numero){
   if($numero==1)
    return 1;
   else
    return $numero + somatorio($numero-1);
  }
 ?>
 </body>
</html>

Fatorial com Recursão

Explicamos o que é e como calcular em:
Fatorial com laços em PHP

Veja que:
5! = 5 x 4 x 3 x 2 x 1
6! = 6 x 5 x 4 x 3 x 2 x 1 = 6 x 5!

Ou seja:
n! = n * (n-1)!

Por definição, 0!=1 e esse será nosso ponto de parada.
Nosso código fica:
<html>
 <head>
  <title>Apostila PHP Progressivo</title>
 </head>
 <body>
 <form action="" method="get">
  Fatorial de de: <input type="number" name="number" /><br />
  <input type="submit" name="submit" value="Calcular" />
 </form> 
 <?php
  $numero = $_GET['number'];
  echo "O fatorial de $numero é : ".fat($numero);
  
  function fat($numero){
   if($numero==0)
    return 1;
   else
    return $numero * fat($numero-1);
  }
 ?>
 </body>
</html>

Fibonacci com Recursão

Já falamos sobre isso em:
Sequência de Fibonacci com Laços

Faremos, por definição:
F(0) = 0;
F(1) = 1;

E a fórmula com recursividade é:
F(n) = F(n-1) + F(n-2);

O ponto de parada é quando n for 0 ou 1, veja como exibir a sequência de Fibonacci usando recursão:
<html>
 <head>
  <title>Apostila PHP Progressivo</title>
 </head>
 <body>
 <form action="" method="get">
  Fatorial de de: <input type="number" name="number" /><br />
  <input type="submit" name="submit" value="Calcular" />
 </form> 
 <?php
  $numero = $_GET['number'];
  echo "O termo $numero é: ".fibo($numero);
  
  function fibo($numero){
   if($numero==0 || $numero==1)
    return $numero;
   else
    return (fibo($numero-1) + fibo($numero-2));
  }
 ?>
 </body>
</html>