title: Recursión global
text: # Recursión global
  
  En la teoría de la computabilidad, la recursión global es una técnica para definir funciones aritméticas por recursión . En una definición de una función f por recursión global, el valor de f(n) se calcula a partir de la secuencia $\langle f(0),f(1),\ldots ,f(n-1)\rangle$ .
  El hecho de que tales definiciones se puedan simplificar muestra que son recursivas primitivas. A diferencia de la recursión global, en la recursión primitiva el cálculo de una función requiere únicamente el valor anterior. Por ejemplo; para una función recursiva primitiva 1-aria g, el valor de g(n +1) se calcula solo a partir de g(n) y n .
  
  # Recursión global
  ## Definición y ejemplos
  
  La función factorial n! se define recursivamente por las reglas
      $0!=1,$
      $(n+1)!=n!(n+1).$
  Esta recursión es primitiva porque calcula el siguiente valor (n +1)! de la función utilizando el valor n y el valor anterior n! Por otro lado, la función Fib(n), que devuelve el n -ésimo número de Fibonacci, se define con las ecuaciones de recursión
      $Fib(0)=0,$
      $Fib(1)=1,$
      $Fib(n+2)=Fib(n+1)+Fib(n).$
  Para calcular Fib(n+2), se requieren los dos últimos valores. Finalmente, considere la función g definida mediante las ecuaciones de recurrencia
      $g(0)=0,$
      $g(n+1)=\sum _{i=0}^{n}g(i)^{n-i}.$
  Si bien los ejemplos anteriores utilizaban un número fijo de valores anteriores, g depende de un número variable de valores anteriories. En particular, g(n+1) requiere todos sus valores anteriores. Utilizando la Numeración de Gödel, podemos definir una función de recursión global como
      $f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )$
  donde $\langle f(0),f(1),\ldots ,f(n-1)\rangle$ es el número de Gödel que codifica la secuencia indicada.
      $f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )$ .
      ${\bar {f}}(0)=\langle \rangle$ ,
      ${\bar {f}}(n+1)={\mathit {a{\tilde {n}}adir}}(n,{\bar {f}}(n),h(n,{\bar {f}}(n))),$
  
  # Recursión global
  ## Equivalencia a recursión primitiva
  
  Dada la función por recursión global f:
      ${\bar {f}}(n)=\langle f(0),f(1),\ldots ,f(n-1)\rangle$
  Basta con definir una función auxiliar para expresarla en un esquema de recursión primitiva
      ${\bar {f}}(n)=\langle f(0),f(1),\ldots ,f(n-1)\rangle$
  De este modo ${\bar {f}}(n)$ codifica los primeros n valores de f. La función ${\bar {f}}$ es primitiva recursiva ya que ${\bar {f}}(n+1)$ se obtiene añadiendo a ${\bar {f}}(n)$ el nuevo elemento $h(n,{\bar {f}}(n))$ :
      ${\bar {f}}(0)=\langle \rangle$ ,
      ${\bar {f}}(n+1)={\mathit {append}}(n,{\bar {f}}(n),h(n,{\bar {f}}(n))),$
      ${\bar {f}}(n+1)=g(n,{\bar {f}}(n))$
  Utilizando ${\bar {f}}$, la función original f se puede definir por $f(n)={\bar {f}}(n+1)[n]$, lo que demuestra que también es una función recursiva primitiva.