Representación matemática de la función de recursión

Question

Bueno, no soy muy bueno en matemáticas, pero tengo la siguiente tarea: Aquí está el código:

int foo(n):
    if n <= 0:
        return 1
    else:
        return foo(n-1)+foo(n-3)-1

¿Qué devolverá foo(7)?

Así que tengo que responder sin usar ningún dispositivo. Y la idea de dibujar árboles a mano me desconcierta. ¿Hay alguna manera de representar dicha función en una fórmula matemática simple sin matemáticas profundas =) Y cuál es la fórmula para esta función.

Answer 1

Pista: ¿Qué es foo(1)? foo(2)? foo(3)? Deberías ver un patrón.

Answer 2

Simplemente hazlo a mano

foo(7)=foo(6)+foo(4)-1

foo(6)=foo(5)+foo(3)-1

...

foo(1)=foo(0)+foo(-2)-1=1+1-1=1

rellenar los pasos intermedios y volver a enchufar

Answer 3

En cuanto a encontrar una forma cerrada, sería mucho más difícil que los métodos que han sugerido Ricky y Cameron. Por ejemplo, una función doblemente recursiva más conocida es la que permite calcular la secuencia de Fibonacci: para un tamaño suficientemente grande $n$ , $fib(n)=fib(n-1)+fib(n-2)$ Así se obtiene la conocida secuencia $1,1,2,3,5,8,13,..$ . Pero la solución de forma cerrada es $$\frac{\phi^n-\psi^n}{\sqrt{5}}$$ ( $\phi$ es la media de oro; $\psi$ es su inversa).