CES-10 INTRODUÇÃO À
COMPUTAÇÃO
Aulas Práticas – 2014
Capítulo IX
Subprogramação e Recursividade
Programa 9.1: Subprograma bem simples para somar
#include <stdio.h>
#include <stdlib.h>
int soma (int x, int y)
{return x + y;}
Copiar, salvar e
executar
int main ( ) {
int a, b, c;
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
c = soma (a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
Programa 9.2: Mesmo efeito, porém sem retornar valor
#include <stdio.h>
#include <stdlib.h>
void soma (int *z, int x, int y)
{*z = x + y;}
Copiar, salvar e
executar
int main ( ) {
int a, b, c;
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
soma (&c, a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
#include <stdio.h>
#include <stdlib.h>
void soma (int *z, int x, int y)
{*z = x + y;}
Função main
int main ( ) {
int a, b, c;
a
b
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
soma (&c, a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
c
#include <stdio.h>
#include <stdlib.h>
void soma (int *z, int x, int y)
{*z = x + y;}
Função main
int main ( ) {
int a, b, c;
a
b
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
soma (&c, a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
Leitura de a e b:
151
346
c
#include <stdio.h>
#include <stdlib.h>
void soma (int *z, int x, int y)
{*z = x + y;}
Função main
int main ( ) {
int a, b, c;
a 151
b 346
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
soma (&c, a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
Leitura de a e b:
151
346
c
Função soma
#include <stdio.h>
#include <stdlib.h>
x
y
z
void soma (int *z, int x, int y)
{*z = x + y;}
Função main
int main ( ) {
int a, b, c;
a 151
b 346
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
soma (&c, a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
Alocação das variáveis de soma
c
Função soma
#include <stdio.h>
#include <stdlib.h>
x
y
z
void soma (int *z, int x, int y)
{*z = x + y;}
Função main
int main ( ) {
int a, b, c;
a 151
b 346
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
soma (&c, a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
c
Passagem dos argumentos aos parâmetros
Função soma
#include <stdio.h>
#include <stdlib.h>
x 151
y 346
z
void soma (int *z, int x, int y)
{*z = x + y;}
Função main
int main ( ) {
int a, b, c;
a 151
b 346
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
soma (&c, a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
c
Passagem dos argumentos aos parâmetros
Função soma
#include <stdio.h>
#include <stdlib.h>
x 151
y 346
z
void soma (int *z, int x, int y)
{*z = x + y;}
Função main
int main ( ) {
int a, b, c;
a 151
b 346
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
soma (&c, a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
z recebeu o endereço de c
z é um ponteiro (apontando para c)
c
Função soma
#include <stdio.h>
#include <stdlib.h>
x 151
y 346
z
void soma (int *z, int x, int y)
{*z = x + y;}
Função main
int main ( ) {
int a, b, c;
a 151
b 346
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
soma (&c, a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
O local cujo endereço está em z (*z)
recebe o valor de x+y
c 497
Função soma
#include <stdio.h>
#include <stdlib.h>
x 151
y 346
z
void soma (int *z, int x, int y)
{*z = x + y;}
Função main
int main ( ) {
int a, b, c;
a 151
b 346
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
soma (&c, a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
Desalocação das variáveis de soma
c 497
#include <stdio.h>
#include <stdlib.h>
void soma (int *z, int x, int y)
{*z = x + y;}
Função main
int main ( ) {
int a, b, c;
a 151
b 346
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
soma (&c, a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
Desalocação das variáveis de soma
c 497
#include <stdio.h>
#include <stdlib.h>
void soma (int *z, int x, int y)
{*z = x + y;}
Função main
int main ( ) {
int a, b, c;
a 151
b 346
printf ("Digite a e b: ");
scanf ("%d%d", &a, &b);
soma (&c, a, b);
printf ("\nc = a + b = %d + %d = %d", a, b, c);
printf ("\n\n"); system ("pause"); return 0;
}
Será escrito:
c 497
c = a + b = 151 + 346 = 497
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
int fat (int
int f;
if (n < 0)
else if (n
else f = n
return f;
}
n) {
f = -1;
<= 1) f = 1;
* fat(n - 1);
Programa 9.3: Cálculo
recursivo de fatorial
Formula recursiva
n! =
-1, para n < 0
1, para 0 ≤ n ≤ 1
n * (n-1)!, para n > 1
Copiar, salvar e
executar
int main() {
int n;
printf ("Calculo de fatorial de n");
printf ("\n\n\tDigite n: ");
scanf ("%d", &n);
printf ("\n\tFat(%d) = %d", n, fat(n));
printf ("\n\n"); system ("pause"); return 0;
}
int v = 0;
//Numero da versao de fat: global
int fat (int n) {
Programa 9.4: Cálculo
int f;
recursivo instrumentado
int i;
de fatorial
v++;
printf ("\n");
for (i = 1; i <= v; i++) printf ("
");
printf ("Entrada em fat versao %d; n = %d; ", v, n);
printf ("Digite algo: "); getche (); printf ("\n");
if (n < 0) f = -1;
Alterar a função fat do
else if (n <= 1) f = 1;
programa anterior
else f = n * fat(n - 1);
printf ("\n");
for (i = 1; i <= v; i++) printf ("
");
printf ("Saida de fat versao %d; n = %d; fat = %d; ",
v, n, f);
printf ("Digite algo: "); getche (); printf ("\n");
v--;
if (v == 0) printf ("\n");
Copiar, salvar e
return f;
executar
}
Exercício 9.1: Potência de expoentes inteiros e não
negativos
An (n inteiro e não negativo)

Escrever um programa para implementar a seguinte fórmula
recursiva:
An =

1, para n = 0
A * An-1, para n > 0
A função main pode ser parecida com a do programa do
fatorial
Exercício 9.2: Raiz quadrada

Escrever um programa para implementar a seguinte fórmula
recursiva:
a, p/ (|a2 - n| < e)
RaizQuad (n, a, e) = RaizQuad (n, (a2+n)/(2*a), e),
caso contrário

a é uma aproximação para a raiz quadrada; e é a precisão
desejada

A primeira aproximação e a precisão devem ser lidas na
função main
Exercício 9.3: Números de Fibonacci (procriação de coelhos)

Gerar a sequência de números de Fibonacci para um dado
valor de n, usando a seguinte fórmula recursiva:
Fib (n) =
-1, p/ n < 0
0, p/ n = 0
1, p/ n = 1
Fib (n-2) + Fib (n-1), p/ n > 1

O programa deve montar uma tabela com os números de
Fibonacci e com o número de chamadas recursivas para
gerar cada um deles

Para tanto, o programa deve ser devidamente instrumentado
(ver como exemplo a tabela a seguir)
Exemplo: tabela para n = 20
n |
Fib(n) | Chamadas recursivas
-------------------------------------------------------0 |
0 |
1
1 |
1 |
1
2 |
1 |
3
3 |
2 |
5
4 |
3 |
9
5 |
5 |
15
6 |
8 |
25
7 |
13 |
41
8 |
21 |
67
9 |
34 |
109
10 |
55 |
177
11 |
89 |
287
12 |
144 |
465
13 |
233 |
753
14 |
377 |
1219
15 |
610 |
1973
16 |
987 |
3193
17 |
1597 |
5167
18 |
2584 |
8361
19 |
4181 |
13529
20 |
6765 |
21891
Tarefa 1 do Lab 9: Função binomial

Em Análise Combinatória, o coeficiente binomial tem a
seguinte formulação recursiva:
Binom (n, k) =

-1, p/ n < 0, k < 0 ou k >n
1, p/ k = 0 ou k = n
Binom (n-1, k-1) + Binom (n-1, k), p/ outros casos
Usando esta formulação, escrever um programa para ler um
inteiro positivo m e montar duas matrizes quadradas:


A primeira de nome A(m x m), onde
A[i][j] = Binom (i, j), para 0  i  m-1 e 0  j  m-1
A segunda de nome B(m x m), onde B[i][j] deverá conter
o número de chamadas recursivas para calcular A[i][j],
para 0  i  m-1 e 0  j  m-1
Exemplo: matrizes para m = 8
Matrizes quadradas com valores e chamadas recursivas da funcao binomial
Digite a dimensao das matrizes: 8
Matriz A com os valores da funcao binomial:
1
1
1
1
1
1
1
1
-1
1
2
3
4
5
6
7
-1
-1
1
3
6
10
15
21
-1
-1
-1
1
4
10
20
35
-1
-1
-1
-1
1
5
15
35
-1
-1
-1
-1
-1
1
6
21
-1
-1
-1
-1
-1
-1
1
7
-1
-1
-1
-1
-1
-1
-1
1
i
j
Matriz B com os numeros de chamadas recursivas da funcao binomial:
1
1
1
1
1
1
1
1
1
1
3
5
7
9
11
13
1
1
1
5
11
19
29
41
1
1
1
1
7
19
39
69
1
1
1
1
1
9
29
69
j
1
1
1
1
1
1
11
41
1
1
1
1
1
1
1
13
1
1
1
1
1
1
1
1
i
Tarefa 2 do Lab 9: Função com aninhamento de
recursividade

Uma função h(n) tem a seguinte formulação recursiva
aninhada:
h (n) =

-1, p/ n < 0
0, p/ n = 0
n, p/ n > 4
h (2 + h (2*n)), p/ 1 ≤ n ≤ 4
Usando esta formulação, escrever um programa para ler um
inteiro positivo m e montar uma tabela de h(n) e do número
de chamadas recursivas para o cálculo de h(n), para 0  n  m
Exemplo: tabela para m = 8
n |
h(n) | Chamadas recursivas
-------------------------------------------------------0 |
0 |
1
1 |
14 |
7
2 |
12 |
5
3 |
8 |
3
4 |
10 |
3
5 |
5 |
1
6 |
6 |
1
7 |
7 |
1
8 |
8 |
1
Tarefa 3 do Lab 9: Função Ackermann

Uma importante função teórica conhecida como função de
Ackermann tem a seguinte formulação recursiva:
Acker (m, n) =

-1, p/ m < 0 ou n < 0
n+1, p/ m = 0 e n ≥ 0
Acker (m-1, 1) p/ n = 0 e m > 0
Acker (m-1, Acker (m, n-1), p/ outros casos
Usando esta formulação, escrever um programa para ler dois
inteiros positivos p e q e montar duas matrizes:


A primeira de nome A(p x q), onde
A[i][j] = Acker (i, j), para 0  i  p-1 e 0  j  q-1
A segunda de nome B(p x q), onde B[i][j] deverá conter o
número de chamadas recursivas para calcular A[i][j], para
0  i  p-1 e 0  j  q-1
Exemplo: matrizes para p = 4 e q = 8
Matrizes com valores e chamadas recursivas da funcao ackermann
Digite as dimensoes das matrizes: 4 8
Matriz A com os valores da funcao acker:
1
2
3
5
2
3
5
13
3
4
7
29
4
5
9
61
5
6
11
125
6
7
13
253
7
8
15
509
8
9
17
1021
i
j
Matriz B com os numeros de chamadas recursivas da funcao acker:
1
2
5
15
1
4
14
106
1
6
27
541
1
8
44
2432
1
10
65
10307
j
1
12
90
42438
1
14
119
172233
1
16
152
693964
i