Summary  
This chapter covers recursion, detailing how to define a base case and a recursive case so a function calls itself with simpler inputs, and explains how the call stack manages these nested calls.  

General domain of usage  
Processing tree data structures

Uma **função recursiva** é uma função que chama a si mesma para resolver um problema dividindo-o em partes menores e mais simples.



Definição

Os principais elementos da recursão são:
- **Caso base**: a condição que interrompe a recursão;
- **Caso recursivo**: a parte em que a função chama a si mesma com uma entrada mais simples.

## Por que usar recursão?

Alguns problemas podem ser naturalmente expressos em termos de subproblemas menores. A recursão oferece uma forma clara e elegante de resolvê-los, fazendo com que uma função chame a si mesma para lidar com casos mais simples. É comumente utilizada em tarefas como processamento de árvores, exploração de caminhos ou decomposição de estruturas (por exemplo, listas, strings).



def print_message(message, times):
    if times > 0:                              # Base case: stop when times is 0
        print(message)
        print_message(message, times - 1)     # Recursive case

print_message("Hello, Recursion!", 3)

Siga passo a passo para entender como isso funciona:

1. `times = 3` → condição é verdadeira, imprime a mensagem, chama `print_message(message, 2)`;
2. `times = 2` → condição é verdadeira, imprime a mensagem, chama `print_message(message, 1)`;
3. `times = 1` → condição é verdadeira, imprime a mensagem, chama `print_message(message, 0)`;
4. `times = 0` → condição é falsa, a recursão para.

**Resultado**: a mensagem é impressa três vezes.



## A Pilha de Chamadas

Cada vez que a função chama a si mesma, ela adiciona um novo quadro à **pilha de chamadas** — uma estrutura de memória que rastreia as chamadas de função ativas. Quando o caso base é alcançado, cada chamada anterior é concluída uma a uma em ordem reversa.

Toda função recursiva deve ter um caso base. Sem isso, a função continuará se chamando indefinidamente e causará um `RecursionError`.

Nota

import unittest

def _dynamic_test(test_case, condition, success_message, failure_message):
    if condition:
        test_case._testMethodName = success_message
        test_case.assertTrue(True, success_message)
    else:
        test_case._testMethodName = failure_message
        test_case.fail(failure_message)

class TestListSum(unittest.TestCase):

    def test_list_sum_basic(self):
        import user_code
        try:
            result = user_code.list_sum([1, 2, 3, 4, 5])
            expected = 15
            condition = result == expected
            failure_message = f"Expected `{expected}` for `[1, 2, 3, 4, 5]`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, f"The `list_sum` returns `15` for `[1, 2, 3, 4, 5]`.", failure_message)

    def test_list_sum_another_list(self):
        import user_code
        try:
            result = user_code.list_sum([10, 20, 30])
            expected = 60
            condition = result == expected
            failure_message = f"Expected `{expected}` for `[10, 20, 30]`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, f"The `list_sum` returns `60` for `[10, 20, 30]`.", failure_message)

    def test_list_sum_empty(self):
        import user_code
        try:
            result = user_code.list_sum([])
            expected = 0
            condition = result == expected
            failure_message = f"Expected `{expected}` for an empty list, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, "The `list_sum` correctly returns `0` for an empty list.", failure_message)

    def test_recursion_used(self):
        import user_code
        import inspect
        try:
            source = inspect.getsource(user_code.list_sum)
            condition = "list_sum(" in source.split("def list_sum")[1]
            failure_message = "Expected `list_sum` to call itself recursively."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, "The `list_sum` function uses recursion.", failure_message)

if __name__ == '__main__':
    unittest.main()

test_main.py

Adquira uma compreensão sólida de como as funções moldam a programação em Python. Domine a definição e chamada de funções, o trabalho com argumentos, o tratamento de valores de retorno e a criação de código flexível e eficiente utilizando recursão e expressões lambda.

Explore o que são funções e por que elas são essenciais em Python. Aprenda a criar funções, definir argumentos, manipular valores de retorno e usar funções embutidas de forma eficaz.

Aprenda como argumentos posicionais e opcionais funcionam em Python. Desenvolva funções adaptáveis que lidam com diferentes entradas e aumentam a flexibilidade do seu código.

Compreensão de como trabalhar com argumentos arbitrários e argumentos nomeados para lidar com tamanhos de entrada variáveis. Aprendizado de como essas técnicas tornam suas funções mais dinâmicas e organizadas.

Descubra como os valores de retorno representam a saída de uma função. Aprenda a retornar valores únicos ou múltiplos, utilizar None e explorar geradores para um controle de fluxo de dados mais avançado.

Desbloqueie conceitos avançados de funções com recursão e funções lambda. Aprenda como a recursão resolve problemas repetitivos e como as expressões lambda criam funções concisas de uma linha.

Recursão

Por que usar recursão?

Um Exemplo Simples

A Pilha de Chamadas

Solução