1
$\begingroup$

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.

  • 0
    Your $foo(n)$ is a flat function with value $1$, unless you are going to change your question to something else later.2012-05-14

3 Answers 3

0

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

0

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

  • 0
    @CameronBuie Thanks for catching that!2012-05-13
0

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.)

  • 0
    How is your answer helping this question?2012-05-14