Recursividade

Recursividade é quando uma função chama a mesma função dentro dela mesma.
Vários problemas podem ser resolvidos com recursão. Para criarmos uma função recursiva primeiramente precisamos analisar o problema e entender a sequência para definirmos quando a função deverá sair da recursividade e retornar algum valor.
Por exemplo a série de Fibonacci. [1,1,2,3,5,8,13...]
Vamos criar uma função que calcule o valor da série e acordo com o índice que passamos. Se passarmos o número 3 a função tem que retornar o número 2 como resposta, se passarmos o número 6 como parâmetro a função tem que retornar o número 8 como resposta e assim sucessivamente.
Analisando o série concluímos que quando o parâmetro passado for 1 o retorno será 1, quando for 2 o retorno será 1, quando for 3 o retorno será 2, esses serão os retornos que farão com que a função saia da recursão.
Obs: estou fazendo dessa forma para ficar bem fácil de entender recirsividade

def fib_rec(n):
# essa é a condição que fará com que a função pare de chamar ela mesma 
 if n==1 or n==2:
  return 1 # e retorne algum valor, que nos dois casos será 1
# o retorno da função se não entrar no if que termina a recursão é ela chamar
# ela mesmo diminuindo o valor do parâmetro por 1 e depois por 2 e somar os resultados
# a função vai diminuindo o valor de n até que entre na função que para a recursão
 return fib_rec(n-1) + fib_rec(n-2) 

Nos comentários do código acima explico detalhadamente como a função funciona e consequentemente a recursividade.
Qualquer dúvida postem nos comentários.