Creo que tu problema está ahí:
Cita:
Iniciado por elchache 
int SumaRecursiva(int a, int b)
{
int resultado;
if (b == 0)
{
resultado = a;
}
else
{
resultado = a+SumaRecursiva(a, b-1);
}
return resultado;
}
Imagina que tienes 4*5 como pusiste. El programa hace:
resultado = 4(b=5) +4(b=4) + 4(b=3) +4 (b=2) + 4(b=1)
Pero entonces haces esto:
resultado = 4
Porqué en el caso b=0 estás asignando, no sumando.
Yo te aconsejaría hacer un for:
for(i=0; i<b; i++){
resultado += a;
}