Python Tutorial - Função Recursiva

1. O que é a função recursiva Python
2. Limitação da recursividade
3. Vantagem da recursividade
4. Desvantagem da Recurssão

Nesta seção, você aprenderá a função recursiva Python.

O que é a função recursiva Python

Uma função recursiva é uma função que se chama a si mesma e a este processo chama-se recursividade de função.

Por exemplo, vamos calcular o factorial de um número, por exemplo, 6.

6 * 5 * 4 * 3 * 2 * 1

No código a seguir, é criada uma função recursiva que encontra o fatorial de um número:

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


a = 6
print("Factorial of", a, "=", fact(a))

Factorial of 6 = 720

A função fact(n) é uma função recursiva. A função fact(n) é uma função recursiva. A função fact(n) chama-se a si mesma com o argumento n-1 até que o número se torne 1 e é assim que o fatorial é calculado, ou seja, multiplicando o número pelo fatorial de um número a menos que o número.

Nesta função recursiva, há uma condição básica que é quando o número se torna 1, 1 é retornado e desta forma a chamada recursiva torna-se finita.

Ao criar uma função recursiva, deve haver uma condição básica para terminar essa chamada recursiva.

Limitação da recursividade

Como já reparou, sempre que a função se chama a si própria, precisa de alguma memória para armazenar alguns valores intermédios. Portanto, a função recursiva consome muito mais memória do que uma função normal não recursiva. Python define a limitação das chamadas recursivas como 3000.

>>> import sys
>>> sys.getrecursionlimit()
3000

Ele aumenta um RecursionError se a recursividade exceder 3000.

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(4000))

Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    print(factorial(4000))
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  [Previous line repeated 989 more times]
  File "<pyshell#1>", line 2, in factorial
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Solução para Remover Limitação de Recursividade

Você poderia resolver a limitação de recorrência definindo a limitação de recorrência para um número maior do que a recorrência necessária.

import sys

sys.setrecursionlimit(5000)


def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(4000))

Vantagem da recursividade

• Usando funções recursivas, o problema pode ser dividido em sub-problemas que podem ser resolvidos facilmente.
• O código torna-se puro e limpo.

Desvantagem da Recurssão

• Por vezes é difícil seguir através da lógica da função recursiva.
• Para resolver cada sub-problema vai levar muito tempo, por isso as funções recursivas são ineficientes.