Exemplo 3 de algoritmo recursivo - "quebrando" o problema em dois, fazendo duas chamadas recursivas.

import java.lang.Exception; class Produto3 {     static Exception e = new Exception();     static int prod (int a, int b) {         System.out.println ("a="+a+" b="+b);         int retVal=0;         e = new Exception();         e.printStackTrace();         if (b==1) {             return a;                 }         retVal=prod(a,b/2);         e = new Exception();         e.printStackTrace();         retVal+=prod(a,b/2);         if ((b%2)==1) {             // b é impar             retVal+=a;         }         System.out.println ("a="+a+" b="+b);         e = new Exception();         e.printStackTrace();         return retVal;     }          public static void main (String[] args) {         System.out.println (prod (3, 5));         System.out.println ("fim do main");     } }

Java2html

O aspecto mais relevante, neste momento da disciplina, é a sequência de invocações e retornos dos métodos. Neste exemplo particular é uma árvore binária.

Nesta solução, fazer duas invocações (chamadas) recursivas é uma possibilidade, idéia que pode ser notada como: prod(a,b)= prod (a,b/2) + prod (a,b/2) + ((b%2)==1)?a:0. Como notado em aula, esta solução é menos eficiente que a do exemplo 2. Através do cálculo da complexidade assintótica (assunto das próximas aulas) é possível mostrar que a função de complexidade de tempo desta solução pertence à mesma classe da função de complexidade da solução 1.