Pessoas com experiência em programação devem estar familiarizadas com funções recursivas. Freqüentemente usamos recursão para resolver uma série de problemas complexos. Algoritmos recursivos são muito eficazes para a maioria dos problemas e também podem otimizar nosso código. ao usar recursão:
1) Recursão é chamar a própria função dentro da própria função.
2) A eficiência da recursão é relativamente baixa e não é recomendado utilizá-la se houver limite de tempo.
3) É necessário que haja uma condição final clara no processo recursivo, ou seja, a saída recursiva.
Vamos explicar as funções recursivas em detalhes abaixo.
Vejamos primeiro o uso simples da recursão por meio de um exemplo:
m=int(input('Digite um número:'))deftest(x):x+=2ifx<100:test(x)else:print('O último x é:',x)test(m)A saída é:
Digite um número: 20 e o último x é: 100
Vamos analisar este exemplo. Primeiro, na primeira linha do código, inserimos um número inteiro, m é passado como um parâmetro real para o método test(), x será adicionado por. 2 primeiro e, em seguida, um julgamento, se o valor de x for menor que 100, chame esta função novamente. Ao chamar, o valor atual de x é usado como o parâmetro real para participar da chamada. =100 está satisfeito.
Observe o diagrama abaixo:
Ou seja, se as condições não forem atendidas, ele retorna para a camada mais externa e chama esta função.
Ao falar sobre problemas clássicos em algoritmos recursivos, a sequência de Fibonacci e a Torre de Hanói são sempre inseparáveis. Aqui explicaremos como usar a recursão para resolver a sequência de Fibonacci.
Primeiro de tudo, precisamos saber que a fórmula recursiva da sequência de Fibonacci é F(n)=F(n-1)+F(n-2), F(1) e F(2) são 1. Nós pode usar recursão para encontrar o valor de um item na sequência de Fibonacci.
Existem muitas maneiras que podemos usar para resolver problemas de sequência de Fibonacci.
Primeiro usamos o método recursivo comumente usado para resolver este problema:
N=int(input(insira o número de itens a serem obtidos:))deffibonacci(n):ifn<=2:#Se for menor ou igual a 2, defina n como 1 return1else:returnfibonacci(n-1) +fibonacci(n-2)print('O valor correspondente é',fibonacci(n))A saída é:
Digite o número de itens que deseja obter: 4 corresponde a 3
Para este método de chamada recursiva, ao inserirmos o valor 4, as seguintes operações serão realizadas recursivamente:
fibonacci(3)+fibonacci(2)=fibonacci(2)+fibonacci(1)+fibonacci(2)
Então podemos ver que o valor do quarto termo é 1+1+1=3.
Na verdade, este método de resolução é uma perda de tempo porque são necessárias muitas iterações. Também podemos usar espaço em vez de tempo para resolver este problema.
O código é o seguinte:
n=int(input(insira o número de termos a serem obtidos:))fibonacci=[1,1]foriinrange(2,n):fibonacci.append(fibonacci[i-1]+fibonacci[i-2])print ('O valor correspondente é',fibonacci[n-1])A saída é:
Digite o número de itens que deseja obter: 4 corresponde a 3
Desta forma, primeiro especificamos os valores dos dois primeiros itens da lista e, em seguida, para o número n de itens que queremos resolver, preenchemos diretamente a lista de números de Fibonacci até o item que precisamos através da fórmula, e finalmente de acordo com o índice O valor encontra diretamente o resultado de saída correspondente.
É isso para a função recursiva. Como mencionado acima, devemos prestar atenção especial à saída recursiva e aos limites de tempo. A saída é a chave para o fim da recursão. exceder o tempo especificado, neste momento precisamos mudar nosso pensamento para resolver o problema.