New answers tagged recursion
1
A recursive call is no different than any other call. Here is what happens when you call procedure X:
The current address is pushed into the stack.
Jump to the beginning of X.
When X concludes, pop the return address from the stack, and jump there.
It doesn't matter whether X is the current procedure or a different one.
1
The base case works because, if the array contains only 2 elements, it compares them and return the biggest.
Starting from this assumption, the recursive call to the function maxNumber compare the maxnumber of the precedent call to the next element in the array.
when the list has been read all the way to the end, the algorithm will return the max number of ...
2
First, you can get the the result from the second xase of master theorem. Second, you have a mistake in your exapnsion:
$$T(n) = 2T(\frac{n}{2}) + n\log(n) = 2(2T(\frac{n}{2^2} + \frac{n}{2}\log(\frac{n}{2})) + n\log(n) = n\log(n) + n\log(\frac{n}{2}) + 2^2T(\frac{n}{2^2}) = n\log(n) + n\log(\frac{n}{2}) + 2^2(2T(\frac{n}{2^3} + \frac{n}{2^2}\log(\frac{n}{...
1
There's an example staring at you in the face: write a function that takes two arguments a and b and returns the sum of the integers from 0 to a, plus b.
Here's another example: write a function that returns the last element of a list, or a special value if the list is empty.
let rec last l =
match l with
| [] -> None
| [x] -> Some x
| h::t -&...
0
This is an example:
let rec all_positive l =
match l with
| [] -> true
| x::xs -> if not(x>=0) then false else all_positive xs;;
the is to notice that the function always points to return the value of the next recursive function call AND also does the main computation first. So its not accumulating anything. I don't think it can be done if an ...
0
It automatically implies that $ O(n^4)$ and $\Omega (n^4)$ because of $f(n)\in O(n^4)$ and master theorem $ \Theta (n^4)$.
2
diplodoc explained in the comments one way to solve the recursion. Your recursion is
$$
A_n = 1 + \frac{A_0 + \cdots + A_{n-1}}{n+1}, \quad A_0 = 1.
$$
The trick is to calculate
$$
(n+1)A_n - n A_{n-1} = (n+1 + A_0 + \cdots + A_{n-1}) - (n + A_0 + \cdots + A_{n-2}) = 1 + A_{n-1},
$$
and so $A_n = A_{n-1} + 1/(n+1)$. From here it follows easily that $A_n$ is ...
2
It seems that you have overlooked the fact that $f(n) \in \Theta(n^4)$ already implies both an upper bound of $f(n)\in O(n^4)$ and a lower bound of $f(n)\in \Omega(n^4)$. Intuitively, $\Theta$- notation says that a function grows "as fast as" another function, which means both "at most as fast" and "at least as fast".
Top 50 recent answers are included
