Exercício com recursão

[Gnrtuga]

Olá pessoal, estou a tentar resolver um exercício mas não estou a conseguir o resultado esperado.

o enunciado é este:

Implemente a função incomodam(n) que devolve uma string contendo "incomodam " (a palavra seguida de um espaço) n vezes. Se n não for um inteiro estritamente positivo, a função deve devolver uma string vazia. Essa função deve ser implementada utilizando recursão.

Utilizando a função acima, implemente a função elefantes(n) que devolve uma string contendo a letra da música "Um elefante incomoda muita gente" de 1 até n elefantes. Se n não for maior que 1, a função deve devolver uma string vazia. Essa função também deve ser implementada utilizando recursão.

Observe que, para um elefante, você deve escrever por extenso e no singular ("Um elefante..."); para os demais, utilize números e o plural ("2 elefantes...").

Dica: lembre-se que é possível juntar strings com o operador "+". Lembre-se também que é possível transformar números em strings com a função str().

Dica: Será que neste caso a base da recursão é diferente de n==1 ?

No exemplo de execução abaixo, note que há uma diferença entre como a string é e como ela é interpretada. Na função print o símbolo "\n" é interpretado como quebra de linha

o resultado esperado é este:

print(elefantes.elefantes(4))
Um elefante incomoda muita gente
2 elefantes incomodam incomodam muito mais
2 elefantes incomodam muita gente
3 elefantes incomodam incomodam incomodam muito mais
3 elefantes incomodam muita gente
4 elefantes incomodam incomodam incomodam incomodam muito mais

o resultado que eu estou a obter é este:

Um elefante incomoda muita gente
2 elefantes incomodam incomodam muito mais
Um elefante incomoda muita gente
2 elefantes incomodam muita gente
3 elefantes incomodam incomodam incomodam muito mais
Um elefante incomoda muita gente
2 elefantes incomodam incomodam muito mais
Um elefante incomoda muita gente
2 elefantes incomodam muita gente
3 elefantes incomodam muita gente
4 elefantes incomodam muita gente

e o código que tenho é este:

def elefantes(n):
    if n <= 0:
        return ""
    if n <= 1:
        return "Um elefante incomoda muita gente" + "\r\n"
    else:
        valor = elefantes(n-1)
        return valor + str(n) + " elefantes " + incomodam(n) + " muito mais " + "\r\n" + valor + str(n) + " elefantes incomodam muita gente" + "\r\n"


def incomodam(n):
    if n <= 0:
        return ""
    if n == 1:
        return "incomodam"

    return "incomodam " + incomodam(n-1)

O que é que estou a fazer mal?

Obrigado!

Edited February 25, 2019 at 09:14 AM by Gnrtuga
erro no enunciado

[pwseo]

@Gnrtuga,

Podes começar por simplificar a tua função incomodam(), pois não precisas de um ramo do if para n == 1:

def incomodam(n):
    if n < 1:
        return ''
    else:
        return 'incomodam ' + incomodam(n-1)

Na função elefantes() temos que compreender que há um caso de base para n == 2, mas temos um requisito especial, para devolver '' (a string vazia) caso n < 2, por isso teremos algo deste género:

def elefantes(n):
    if n < 2:
        # devolver ''
    elif n == 2:
        # caso base
    else:
        # caso recursivo

Como chegámos a este caso base? De duas formas: a) o enunciado lê-se que o resultado deve ser '' se o número "não for maior que 1" e b) o próprio output acaba por nos indicar isso, uma vez que o mínimo que o programa emite é:

Um elefante incomoda muita gente
2 elefantes incomodam incomodam muitos mais

Este é o output de elefantes(2). No teu código assumiste erradamente que uma invocação de elefantes(1) poderia devolver a primeira frase, mas essa assunção é incorrecta, tal como indica o enunciado.

Temos, portanto, o seguinte:

def elefantes(n):
    if n < 2:
        return ''
    elif n == 2:
        return 'Um elefante incomoda muita gente\n' + str(n) + ' elefantes ' + incomodam(n) + 'muito mais\n'
    else:
        # caso recursivo

E agora passamos ao caso recursivo. É preciso compreendermos cada caso é composto por 2 frases: uma onde dizemos que n-1 elefantes incomodam muita gente, e outra onde dizemos que n elefantes incomodam(n) muito mais. Neste caso cometeste dois erros:

1. Utilizaste valor duas vezes no resultado, o que significa que cada caso teu vai iniciar duas chamadas recursivas, aumentando o output exponencialmente
2. Estruturaste o código de modo a que seja devolvido que n-1 elefantes incomodam(n-1) muito mais, seguida de que n elefantes incomodam muita gente (o contrário do que eu disse acima)

Se eliminarmos a inclusão desnecessária de valor (e substituirmos a própria variável valor por elefantes(n-1), que é o seu significado), e corrigirmos a ordem das frases, obtemos o seguinte:

def elefantes(n):
    if n < 2:
        return ''
    elif n == 2:
        return 'Um elefante incomoda muita gente\n' + str(n) + ' elefantes ' + incomodam(n) + 'muito mais\n'
    else:
        return elefantes(n-1) + str(n-1) + ' elefantes incomodam muita gente\n' + str(n) + ' elefantes ' + incomodam(n) + 'muito mais\n'

 

Podemos agora escrever um pequeno driver para testar elefantes():

for n in range(1, 5):
    print('Para n = {}'.format(n))
    print(elefantes(n))

Obtém-se o seguinte output:

Para n = 1

Para n = 2
Um elefante incomoda muita gente
2 elefantes incomodam incomodam muito mais

Para n = 3
Um elefante incomoda muita gente
2 elefantes incomodam incomodam muito mais
2 elefantes incomodam muita gente
3 elefantes incomodam incomodam incomodam muito mais

Para n = 4
Um elefante incomoda muita gente
2 elefantes incomodam incomodam muito mais
2 elefantes incomodam muita gente
3 elefantes incomodam incomodam incomodam muito mais
3 elefantes incomodam muita gente
4 elefantes incomodam incomodam incomodam incomodam muito mais

Espero ter ajudado.

 

P.S. Há formas mais idiomáticas de concatenar strings e incluir nelas valores numéricos; não as utilizei pois o enunciado referia explicitamente a utilização do operador + e da função str() para esse efeito (mas resulta em código mais longo, mais feio).

Edited March 5, 2019 at 02:22 PM by pwseo
detalhes menores

[Gnrtuga]

@pwseo muito obrigado pela explicação que está excelente!

Também gostei do driver (nunca tinha ouvido falar) que é uma maneira porreira para testar programas simples.

Mais uma vez, obrigado!