Recursividade - entendendo o conceito recursivo

Olá pessoal, hoje vamos entender e aprender a montar funções recursivas, como estou trabalhando em um novo projeto de python onde vou montar um curso do básico ao avançado, todos os exemplos de hoje serão escritos na linguagem python.

O que é recursividade?

Recursividade pode ser definida como a capacidade que uma função ou subrotina tem de invocar a si mesma, ou seja, definimos uma função como recursiva se esta faz uma chamada a si mesmo. 

Recursividade x Iteração

Quando falamos de recursividade algumas duvidas surgem, como: "Porque não usar iteração ao invés de recursividade?"... bom é um estilo de programação e algumas vezes determinadas soluções não serão possíveis de ser realizadas apenas com iterações (loops). Abaixo os prós e contras da recursividade:

Prós:

• Código elegante;
• Código mais legivel;

Contras:

• Necessidade de mais memória;
• Consome mais processamento; 

Algumas perguntas que você deve estar se fazendo:

• Recursividade só pode ser usanda com linguagem C/C++?

 Não, o conceito é independente da linguagem escolhida. Recursividade pode ser utilizada em qualquer linguagem estruturada ou OO. 

•  Porque quando falamos de recursividade o pessoal só mostra exemplos aplicados em funções que calculam fatorial de um número ou série fibonnacci?

Porque é o jeito mais claro de se apresentar o conceito recursivo. Mais acalme-se pequeno gafanhoto eu vou dar um exemplo mais tranquilo e aplicado ao seu cotidiano.

Vamos aos ... Exemplos!

Vamos exemplificar o conceito programando alguns problemas utilizando-se da recursividade para solucioná-los. 
Abaixo temos o famoso exemplo fatorial utilizando recursividade:

def fatorial (valor):
    if valor == 1 or valor == 0:
        return 1
    else:
        return valor * fatorial(valor-1)

#vamos pedir um valor para o usuario
a = input('Informe um numero: ')
#chamando a funcao e imprimindo o valor que ela retorna
print fatorial(a)

Uma função só é liberada da memória quando ela chega ao seu final. No caso da função fatorial() enquanto o parâmetro valor não for igual a 1, ela não vai ser encerrada (não vai chegar ao seu final) com isso ela persiste com uma referencia ativa na memória e se reexecuta. Com isso uma pilha de valores vai sendo criada na memória e enquanto a função não terminar esse processor vai ser repetido até que haja um estouro de memória ou que a função seja encerrada.

Vamos fazer um exemplo mais tranquilo agora pequeno gafanhoto, vamos fazer um programa que irá imprimir a soma de todos os numeros presentes no intervalo de 1  até X:

# -*- coding: UTF-8 -*-
def soma (n):
    if n == 1:
        return 1
    else:
        return n + soma( n - 1)
      
n = input("Informe um número: ")
print soma(n)

Importante: Deve-se definir uma solução que implica em uma condição de terminação (solução trivial). Outro fator importante é provar que a função decresce a cada passo de repetição.

Dúvidas, sujestões comentem...