What is wrong with the attempts at defining a Recursive Function

138 Views Asked by At

What is wrong with these attempts at defining a recursive function?

(i) $f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 3, f(n) = f(n - 1) + f(n - 2)$ $\quad$$for \ n \ge 2$

(ii) $f(0) = 0, f(n) = f(n - 1) + f(n - 2)$ $\quad$$for \ n \ge 2$

2

There are 2 best solutions below

2
On

i

$f(n) \neq f(n-1) + f(n-2)$ for $n \geq 2$ because $f(3) = 3$ and $f(2) + f(1) = 2$

ii

$f(1)$ is not defined, which is needed to define $f(2)$, which is need to define $f(3)$, ... etc.

0
On

For $i) $, $f (3) $ must be $=2$

For $ii) $, you need $f (1) $ to compute $f (2 ) $.