Lesson 8
Funções e recursão

1. Funções

Lembre-se que na matemática o fatorial de um número n é definido como n! = 1 ⋅ 2 ⋅ ... ⋅ n (como o produto de todos os números inteiros de 1 a n). Por exemplo, 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120. É claro que fatorial é fácil de calcular, usando um loop for. Imagine que precisamos, em nosso programa, calcular o fatorial de vários números várias vezes (ou em diferentes locais de código). Claro, você pode escrever o cálculo do fatorial uma vez e depois usar Copiar-Colar para inseri-lo onde quer que você precise:

None

# compute 3!
res = 1
for i in range(1, 4):
    res *= i
print(res)

# compute 5!
res = 1
for i in range(1, 6):
    res *= i
print(res)

No entanto, se cometermos um erro no código inicial, este código errôneo aparecerá em todos os lugares onde copiamos o cálculo do fatorial. Além disso, o código é mais longo do que poderia ser. Para evitar reescrever a mesma lógica nas linguagens de programação, existem funções.

Funções são as seções de código que são isoladas do resto do programa e executadas somente quando chamadas. Você já conheceu a função sqrt() , len() e print() . Todos eles têm algo em comum: podem receber parâmetros (zero, um ou vários deles) e podem retornar um valor (embora possam não retornar). Por exemplo, a função sqrt() aceita um parâmetro e retorna um valor (a raiz quadrada do número fornecido). A função print() pode ter vários argumentos e não retorna nada.

Agora queremos mostrar a você como escrever uma função chamada factorial() que usa um único parâmetro - o número e retorna um valor - o fatorial desse número.

None

def factorial(n):
    res = 1
    for i in range(1, n + 1):
        res *= i
    return res

print(factorial(3))
print(factorial(5))

Queremos fornecer algumas explicações. Primeiro, o código da função deve ser colocado no início do programa (antes do lugar onde queremos usar a função factorial() , para ser preciso). A primeira linha def factorial(n): deste exemplo é uma descrição da nossa função; a palavra fatorial é um identificador (o nome da nossa função). Logo após o identificador, vai a lista de parâmetros que nossa função recebe (entre parênteses). A lista consiste em identificadores separados por vírgula dos parâmetros; no nosso caso, a lista consiste em um parâmetro n . No final da linha, coloque dois pontos.

Então vai o corpo da função. No Python, o corpo deve estar recuado (por Tab ou quatro espaços, como sempre). Esta função calcula o valor de n! e armazena na variável res . A última linha da função é return res , que sai da função e retorna o valor da variável res .

A declaração de return pode aparecer em qualquer lugar de uma função. Sua execução sai da função e retorna o valor especificado para o local onde a função foi chamada. Se a função não retornar um valor, a instrução de retorno não retornará realmente algum valor (embora ainda possa ser usado). Algumas funções não precisam retornar valores e a instrução de retorno pode ser omitida para eles.

Nós gostaríamos de fornecer outro exemplo. Aqui está a função max() que aceita dois números e retorna o máximo deles (na verdade, essa função já se tornou parte da sintaxe do Python).

10
20

def max(a, b):
    if a > b:
        return a
    else:
        return b

print(max(3, 5))
print(max(5, 3))
print(max(int(input()), int(input())))

Agora você pode escrever uma função max3() que leva três números e retorna o máximo deles.

None

def max(a, b):
    if a > b:
        return a
    else:
        return b

def max3(a, b, c):
    return max(max(a, b), c)

print(max3(3, 5, 4))

A função max() no Python pode aceitar vários argumentos e retornar o máximo deles. Aqui está um exemplo de como tal função pode ser escrita.

None

def max(*a):
    res = a[0]
    for val in a[1:]:
        if val > res:
            res = val
    return res

print(max(3, 5, 4))

2. Variáveis ​​locais e globais

Dentro da função, você pode usar variáveis ​​declaradas em algum lugar fora dela:

None

def f():
    print(a)

a = 1
f()

Aqui a variável a é definida como 1, e a função f() imprime esse valor, apesar do fato de que quando declaramos a função f essa variável não é inicializada. O motivo é, no momento de chamar a função f() (a última string), a variável a já possui um valor. É por isso que a função f() pode exibi-lo.

Tais variáveis ​​(declaradas fora da função mas disponíveis dentro da função) são chamadas globais .

Mas se você inicializar alguma variável dentro da função, você não poderá usar essa variável fora dela. Por exemplo:

None

def f():
    a = 1

f()
print(a)

Recebemos o erro NameError: name 'a' is not defined . Tais variáveis ​​declaradas dentro de uma função são chamadas locais . Eles ficam indisponíveis depois que você sai da função.

O que é realmente encantador aqui é o que acontece se você alterar o valor de uma variável global dentro de uma função:

None

def f():
    a = 1
    print(a)

a = 0
f()
print(a)

Este programa imprimirá os números 1 e 0. Apesar do valor da variável a alterado dentro da função, fora da função permanece a mesma! Isso é feito para "proteger" variáveis ​​globais de mudanças inadvertidas de função. Portanto, se alguma variável for modificada dentro da função, a variável se tornará uma variável local e sua modificação não alterará uma variável global com o mesmo nome.

Mais formalmente: o interpretador Python considera uma variável local para a função, se no código desta função houver pelo menos uma instrução que modifica o valor da variável. Então essa variável também não pode ser usada antes da inicialização. Instruções que modificam o valor de uma variável - os operadores = , += e o uso da variável como um loop for parâmetro. No entanto, mesmo que a instrução de variável variável nunca seja executada, o intérprete não pode verificá-la e a variável ainda é local. Um exemplo:

None

def f():
    print(a)
    if False:
        a = 0

a = 1
f()

Ocorre um erro: UnboundLocalError: local variable 'a' referenced before assignment . Nomeadamente, na função f() o identificador a torna a se uma variável local, uma vez que a função contém o comando que modifica a variável a . A instrução de modificação nunca será executada, mas o intérprete não a verificará. Portanto, quando você tenta imprimir a variável a , recorre a uma variável local não inicializada.

Se você quiser que uma função seja capaz de alterar alguma variável, você deve declarar essa variável dentro da função usando a palavra-chave global :

None

def f():
    global a
    a = 1
    print(a)

a = 0
f()
print(a)

Este exemplo irá imprimir a saída de 1 1, porque a variável a é declarada como global e alterá-la dentro da função faz com que a alteração seja global.

No entanto, é melhor não modificar valores de variáveis ​​globais dentro de uma função. Se a sua função deve alterar alguma variável, deixe-a retornar este valor, e você escolhe ao chamar a função explicitamente atribuir uma variável a este valor. Se você seguir essas regras, a lógica das funções funcionará independentemente da lógica do código e, assim, essas funções poderão ser facilmente copiadas de um programa para outro, economizando seu tempo.

Por exemplo, suponha que seu programa deve calcular o fatorial do número dado que você deseja salvar na variável f. Veja como você não deve fazer isso:

5

def factorial(n):
    global f
    res = 1
    for i in range(2, n + 1):
        res *= i
    f = res

n = int(input())
factorial(n)
print(f)
# fazendo outras coisas com variável f

Este é o exemplo de código ruim , porque é difícil usar outro tempo. Se amanhã você precisar de outro programa para usar a função "fatorial", não será possível copiar apenas essa função e colar o novo programa. Você terá que garantir que esse programa não contenha a variável f .

É muito melhor reescrever este exemplo da seguinte maneira:

5

# início de um pedaço de código que pode ser copiado de um programa para outro
def factorial(n):
    res = 1
    for i in range(2, n + 1):
        res *= i
    return res
# fim do pedaço de código

n = int(input())
f = factorial(n)
print(f)
# fazendo outras coisas com variável f

É útil dizer que as funções podem retornar mais de um valor. Aqui está o exemplo de retornar uma lista de dois ou mais valores:

return [a, b]

Você pode chamar a função dessa lista e usá-la em várias atribuições:

n, m = f(a, b)

3. Recursão

Como vimos acima, uma função pode chamar outra função. Mas funções também podem se chamar! Para ilustrar, considere o exemplo da função de computação fatorial. É bem conhecido que 0! = 1, 1! = 1. Como calcular o valor de n! para grandes n? Se fomos capazes de calcular o valor de (n-1) !, então facilmente calculamos n !, desde que n! = N⋅ (n-1) !. Mas como calcular (n-1) !? Se calculamos (n-2) !, então (n-1)! = (N-1) ⋅ (n-2) !. Como calcular (n-2) !? Se ... No final, chegamos a 0 !, que é igual a 1. Assim, para calcular o fatorial podemos usar o valor do fatorial para um inteiro menor. Esse cálculo pode ser feito usando o Python:

None

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))        

A situação quando a função chama a si mesma é chamada de recursão e essa função é chamada de recursiva.

Funções recursivas são mecanismos poderosos na programação. Infelizmente, nem sempre são eficazes e muitas vezes levam a erros. O erro mais comum é a recursão infinita , quando a cadeia de chamadas de funções nunca termina (bem, na verdade, termina quando você fica sem memória livre no computador). Um exemplo de recursão infinita:

def f():
    return f()

1. Condição de parada incorreta. Por exemplo, se no programa de cálculo fatorial esquecemos de colocar a verificação if n == 0 , então factorial(0) chamará factorial(-1) , que chamará factorial(-2) , etc.
2. Chamada recursiva com parâmetros incorretos. Por exemplo, se a função factorial(n) chamar a função factorial(n) , também obteremos uma cadeia infinita de chamadas.

Portanto, ao codificar uma função recursiva, é necessário primeiro garantir que ela atinja suas condições de parada - para pensar por que sua recursão jamais terminará.