Exemplo 2 de algoritmo recursivo - "quebrando" o problema em dois.

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

Java2html

O cálculo do produto pode ser feito "diminuindo o tamanho do problema de uma unidade" ié: prod(a,b) = a + prod (a, b-1), ou "diminuindo o tamanho do problema pela metade (e dobrando o valor)" ié: prod(a,b) = 2*prod(a,b/2) + ((b%2)==1)?a:0. O tempo de execução da primeira solução é proporcional ao valor de b, o da segunda é proporcional ao log de b na base 2.