Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 =) –  AlexIv 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
show 1 more comment

3 Answers

up vote 0 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.