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.
On
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
On
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.)
Hint: What is foo(1)? foo(2)? foo(3)? You should see a pattern.