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
    What's so hard about a tree?2012-05-13
  • 0
    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 =)2012-05-13
  • 0
    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.2012-05-13
  • 0
    ... 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. :(2012-05-14
  • 0
    $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$2012-05-14
  • 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
    You've changed the plus to a minus in the formula.2012-05-13
  • 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
    you meant $fib(n)=fib(n-1)+fib(n-2)$2012-05-13
  • 0
    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.2012-05-13
  • 0
    Good point, Cameron-quite simple indeed! Thanks, ricky.2012-05-13
  • 0
    How is your answer helping this question?2012-05-14