# Mathmatical representation of recursion function

Well i'm not so good at math, but i have the following task: Here's the code:

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


What's foo(7) will return?

So i have to answer without using any devices. And thoughts about drawing trees by hand puzzles me. Is there any way to represent such function into simple math formula without deep math =) And what's the formula for this function.

-
What's so hard about a tree? –  Joel Cornett May 13 '12 at 22:34
Too big to draw, this task goes with 7, but what if n == 100? I just prefer to understand the task and try to find some abstract common solution =) –  4lex1v May 13 '12 at 22:39
I see. Well even if $n=100$, Since this is a recursive function, you would eventually run into values that you've calculated before. The tree for $f(7)$ (by my calculation) only resulted in 13 nodes. –  Joel Cornett May 13 '12 at 23:01
... which leads to the idea of 'dynamic programming' -- to efficiently compute a recursion like this by computing a table of all values $f(n)$ with $-1 \leq n \leq 7$ in order, with the recursive step simply being "look the value up in a table". And as Cameron's answer notes, if you set about doing this, you would quickly stumble across the easy solution. I am always surprised how reluctant people are to compute things, and dismayed when it prevents them from obtaining a key insight into a problem. :( –  Hurkyl May 14 '12 at 1:36
$f(1) =f(0)+f(-2)-1 = 1+1-1 = 1, f(2)=f(1)+f(-1)-1=1. f(3)=f(2)+f(0)-1=1$ –  Kirthi Raman May 14 '12 at 2:55

Hint: What is foo(1)? foo(2)? foo(3)? You should see a pattern.

-

just do it out by hand

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

fill in steps in between and plug back in

-
You've changed the plus to a minus in the formula. –  Cameron Buie May 13 '12 at 22:31
@CameronBuie Thanks for catching that! –  Steven-Owen May 13 '12 at 22:32

As to finding a closed form, it would be much more difficult than the methods ricky and Cameron have suggested. For instance, a better-known doubly recursive function is the one to compute the Fibonacci sequence: for big enough $n$, $fib(n)=fib(n-1)+fib(n-2)$, so you get the well-known sequence $1,1,2,3,5,8,13,..$. But the closed form solution is $$\frac{\phi^n-\psi^n}{\sqrt{5}}$$ ($\phi$ is the golden mean; $\psi$ is its inverse.)

-
you meant $fib(n)=fib(n-1)+fib(n-2)$ –  Steven-Owen May 13 '12 at 22:37
Actually, in this case, the closed form turns out to be quite simple, but that is an excellent example for why it is not always so. –  Cameron Buie May 13 '12 at 22:37
Good point, Cameron-quite simple indeed! Thanks, ricky. –  Kevin Carlson May 13 '12 at 22:41
How is your answer helping this question? –  Kirthi Raman May 14 '12 at 2:58