Salve,
O pessoal sempre pede sugestão de exercícios para fazer.
Enviarei sugestões periodicamente.
Vocês podem encontrar vários exercícios na página Recursão e algoritmos recursivos.
Sugiro que vocês façam pelo menos o 5, 6 e 10.
Ae pessoal, aproveitando o tópico sobre recursão...
Fiquei curioso sobre as possibilidades de otimização de código que o gcc poderia fazer, especificamente no caso de funções recursivas de cauda, então resolvi experimentar com a função fatorial_r, comparando versões compiladas com e sem otimizações (cf. opção -O2) ...
#include <stdio.h>
#include <stdlib.h>
/*#include <assert.h>*/
int fatorial (int n);
int main(int argc, char const *argv[])
{
int n;
/*if (argc < 2) {
printf("uso: fatorial <inteiro>\n");
exit (EXIT_FAILURE);
}*/
n = atoi (argv[1]);
printf ("fatorial (%d) = %d\n", n, fatorial ( n ));
return EXIT_SUCCESS;
}
int fatorial (int n)
{
/*assert (n >= 0 && "n deve ser não-negativo");*/
if (n <= 1) return 1;
return n * fatorial (n - 1);
}
Primeiro, compilando com gcc forçando nenhuma otimização:
gcc -Wall -ansi -pedantic -O0 -S fatorial_r.c
E, embora não sendo nenhum expert, examinando o código assembly gerado em fatorial_r.s podemos perceber que a chamada recursiva ainda está lá...
.cstring LC0: .ascii "fatorial (%d) = %d\12\0" .text .globl _main _main: LFB6: pushq %rbp LCFI0: movq %rsp, %rbp LCFI1: subq $32, %rsp LCFI2: movl %edi, -20(%rbp) movq %rsi, -32(%rbp) movq -32(%rbp), %rax addq $8, %rax movq (%rax), %rdi call _atoi movl %eax, -4(%rbp) movl -4(%rbp), %edi call _fatorial movl -4(%rbp), %esi movl %eax, %edx leaq LC0(%rip), %rdi movl $0, %eax call _printf movl $0, %eax leave ret LFE6: .globl _fatorial _fatorial: LFB7: pushq %rbp LCFI3: movq %rsp, %rbp LCFI4: subq $16, %rsp LCFI5: movl %edi, -4(%rbp) cmpl $1, -4(%rbp) jg L4 movl $1, -8(%rbp) jmp L6 L4: movl -4(%rbp), %edi decl %edi call _fatorial movl %eax, %edx imull -4(%rbp), %edx movl %edx, -8(%rbp) L6: movl -8(%rbp), %eax leave ret LFE7: .section __TEXT,__eh_frame,coalesced,no_toc+strip_static_syms+live_support EH_frame1: .set L$set$0,LECIE1-LSCIE1 .long L$set$0 LSCIE1: .long 0x0 .byte 0x1 .ascii "zR\0" .byte 0x1 .byte 0x78 .byte 0x10 .byte 0x1 .byte 0x10 .byte 0xc .byte 0x7 .byte 0x8 .byte 0x90 .byte 0x1 .align 3 LECIE1: .globl _main.eh _main.eh: LSFDE1: .set L$set$1,LEFDE1-LASFDE1 .long L$set$1 LASFDE1: .long LASFDE1-EH_frame1 .quad LFB6-. .set L$set$2,LFE6-LFB6 .quad L$set$2 .byte 0x0 .byte 0x4 .set L$set$3,LCFI0-LFB6 .long L$set$3 .byte 0xe .byte 0x10 .byte 0x86 .byte 0x2 .byte 0x4 .set L$set$4,LCFI1-LCFI0 .long L$set$4 .byte 0xd .byte 0x6 .align 3 LEFDE1: .globl _fatorial.eh _fatorial.eh: LSFDE3: .set L$set$5,LEFDE3-LASFDE3 .long L$set$5 LASFDE3: .long LASFDE3-EH_frame1 .quad LFB7-. .set L$set$6,LFE7-LFB7 .quad L$set$6 .byte 0x0 .byte 0x4 .set L$set$7,LCFI3-LFB7 .long L$set$7 .byte 0xe .byte 0x10 .byte 0x86 .byte 0x2 .byte 0x4 .set L$set$8,LCFI4-LCFI3 .long L$set$8 .byte 0xd .byte 0x6 .align 3 LEFDE3: .subsections_via_symbols
No entanto, compilando desta vez com -O2 e verificando o fatorial_r.s gerado, podemos perceber que a chamada recursiva se foi, e que o compilador otimizou o código gerando de fato um laço...
gcc -Wall -ansi -pedantic -O2 -S fatorial_r.c
.text .align 4,0x90 .globl _fatorial _fatorial: LFB7: pushq %rbp LCFI0: movq %rsp, %rbp LCFI1: movl $1, %eax cmpl $1, %edi jg L5 jmp L6 .align 4,0x90 L10: movl %edx, %edi L5: leal -1(%rdi), %edx imull %edi, %eax cmpl $1, %edx jne L10 L6: leave ret LFE7: .cstring LC0: .ascii "fatorial (%d) = %d\12\0" .text .align 4,0x90 .globl _main _main: LFB6: pushq %rbp LCFI2: movq %rsp, %rbp LCFI3: pushq %rbx LCFI4: subq $8, %rsp LCFI5: movq 8(%rsi), %rdi call _atoi movl %eax, %ebx movl %eax, %edi call _fatorial movl %eax, %edx movl %ebx, %esi leaq LC0(%rip), %rdi xorl %eax, %eax call _printf xorl %eax, %eax addq $8, %rsp popq %rbx leave ret LFE6: .section __TEXT,__eh_frame,coalesced,no_toc+strip_static_syms+live_support EH_frame1: .set L$set$0,LECIE1-LSCIE1 .long L$set$0 LSCIE1: .long 0x0 .byte 0x1 .ascii "zR\0" .byte 0x1 .byte 0x78 .byte 0x10 .byte 0x1 .byte 0x10 .byte 0xc .byte 0x7 .byte 0x8 .byte 0x90 .byte 0x1 .align 3 LECIE1: .globl _fatorial.eh _fatorial.eh: LSFDE1: .set L$set$1,LEFDE1-LASFDE1 .long L$set$1 LASFDE1: .long LASFDE1-EH_frame1 .quad LFB7-. .set L$set$2,LFE7-LFB7 .quad L$set$2 .byte 0x0 .byte 0x4 .set L$set$3,LCFI0-LFB7 .long L$set$3 .byte 0xe .byte 0x10 .byte 0x86 .byte 0x2 .byte 0x4 .set L$set$4,LCFI1-LCFI0 .long L$set$4 .byte 0xd .byte 0x6 .align 3 LEFDE1: .globl _main.eh _main.eh: LSFDE3: .set L$set$5,LEFDE3-LASFDE3 .long L$set$5 LASFDE3: .long LASFDE3-EH_frame1 .quad LFB6-. .set L$set$6,LFE6-LFB6 .quad L$set$6 .byte 0x0 .byte 0x4 .set L$set$7,LCFI2-LFB6 .long L$set$7 .byte 0xe .byte 0x10 .byte 0x86 .byte 0x2 .byte 0x4 .set L$set$8,LCFI3-LCFI2 .long L$set$8 .byte 0xd .byte 0x6 .byte 0x4 .set L$set$9,LCFI5-LCFI3 .long L$set$9 .byte 0x83 .byte 0x3 .align 3 LEFDE3: .subsections_via_symbols
É isso ae! GCC é mesmo f*%#!!!!
[]s
Thiago