Hi Jow Forums,
I have an exercise of recursive function to practise. Here:
int nisesap ( int n)
{
int res;
if (n < 0)
{
res = n + 1;
}
else
{
res = nisesap(nisesap(n − 2));
}
return res;
}
The exercise asks:
Prove that nisesap(n) = 0 for all n ≥ 0.
It's calling 2 same functions inside one and I don't know how to raise it.
Other urls found in this thread:
en.wikipedia.org
twitter.com
>muh proof
Absolutely useless
Then, is useless? Is a bad programming exercise?
>do my homework for me
Do you know what induction is?
This isn't stackoverflow
Read your textbook and lecture slides. If you still don't get it go ask your tutor. If that still doesn't work go suck a guys hot juicy cock in exchange for letting you copy his work.
Calculate nisesap(0) and nisesap(1) and see what you can derive from it for nisesap(n) for all n ≥ 2.
What kind of idiot writes it like that? Write
int nisesap(int n) {
if (n < 0) {
return n + 1;
}
return nisesap(nisesap(n - 2));
}
But yeah, calculatue for n = 0 and n = 1 and use induction from there.
it's 0 because of the double call.
if it's 0 it will return n(n(-2)) that's n(-2+1) that's n(-1) that's 0
if it's -1 it's obv -1+1 => 0
Anything below -1 retruns n+1
Anything above 0 counts down to -1 or -2
Did I miss something, this feels too obvious?
The function in OP is:
f(x) = [x=0, f(x-2)
From there we see that the function is not evaluated until its input is negative, which should give you enough clue to continue.
I FUCKING HATE that these are the two acceptable indentation styles.
isolates the contents of each block from the surrounding code. This is a nice idea, but unnecessary, because indentation in the first place already takes care of that. Putting more isolation on top of the isolation provided by indentation just makes it ugly.
is even more of a clusterfuck. It tries to solve the problem by not putting an extra line between the block's header and its contents, but then it puts a pointless extra line between the block's contents and the statements that follow. It's just asymmetric and weird. I guess it helps to show the indentation level of the block being closed, but you should be able to tell that from the indentation level of the next line, regardless of whether that next line is an isolated brace.
This is how I'd do it. Or rather, how I wish I could do it, but can't, because it's not an accepted standard.
int nisesap(int n) {
int res;
if (n < 0) {
res = n + 1; }
else {
res = nisesap(nisesap(n - 2)); }
return res; }
It's not f(x-2), it is f(f(x-2)). That's why you need induction:
At 2 or above you know f(x)=0 for x=0,...,x-2, so it turns into f(0) is trivially 0.
Try putting every number you can think of.
Oh right, my bad, but the important bit is that the function won't be evaluated with a positive number in either case so adding one will just make it zero.
The first step is to prove it's 0 for n = 0.
The next step is to prove that if it's 0 for any x, it must also be 0 for x + 1.
Proving these two things is sufficient to prove the greater claim that it's 0 for all n >= 0.
This is called proof by induction.
Computer proof:
int nisesap (int n) {
return n < 0 ? n + 1 : nisesap(nisesap(n - 2))
}
int nisesap (int n) {
return 0;
}
Well, we know that nisesap(0) = 0
And we know that nisesap(1) = 0
Assume that it's true that nisesap(k) = 0 and it's true that nisesap(k - 1) = 0, k > 0
Then nisesap(k + 1) = nisesap(nisesap(k + 1 - 2)
= nisesap(nisesap(k -1))
= nisesap(0)
= 0
Why would you use induction? Prove it works for 0 and 1 and from there every odd value of n will collapse into f(1) and every even into f(0). I tried pondering on the induction idea but I can't seem to get why would you want to solve it that way.
What kind of idiot writes it like that? Write
(define (nisesap n)
(if (< n 0)
(+ n 1)
(nisesap (nisesap (- n 2)))
)
)
>and from there every odd value of n will collapse into f(1) and every even into f(0).
Yes, by induction this is true.
But doesn't induction involve choosing two arbitrary k and k+1 and proving k+1 through k?
>But doesn't induction involve choosing two arbitrary k and k+1 and proving k+1 through k?
Even with a degree in mathematics I cannot parse this sentence.
>Why would you use induction if you can use induction two times?
That's exactly where I read about k and k+1 your nigger
You choose k, you assume it's true for f(k) and then you prove f(k+1) through the assumption that f(k) holds true.
But I didn't use induction as far as I understand induction. The problem is probably that I don't understand induction.
>But I didn't use induction
You did.
>Prove it works for 0 (base case #1) and 1 (base case #2) and from there every odd value of n (induction step #1) will collapse into f(1) and every even (induction step #2) into f(0).
Oh, seems induction is so intuitive I didn't even know I was using it! Thanks user.
What kind of idiot writes it like that? Write
: NISESAP DUP 0 < IF 1 + ELSE 2 - RECURSE RECURSE THEN ;
nisesap(0) = nisesap(nisesap(0 - 2)) = nisesap(nisesap(-2)) = nisesap(-2 + 1) = nisesap(-1) = -1 + 1 = 0
nisesap(n + 1) = nisesap(nisesap((n + 1 - 2)) = nisesap(nisesap(n - 1)) = nisesap(n - 1 + 1) = nisesap(n) = 0
If this is hard for you, drop out.
Split the problem into { x = 0 }. The first should be apparent, confirm zero, then show x' = (x + 1) follows.
Prove both negative and positive cases.
That's shit. You should be using return in the if statement and the else statement so the compiler can optimize this into an iterative solution.
>retards it should be written like this
this is why you guys can't get jobs
recursion without a debugger can be hard, for noobs.
based and forthpilled
High school math. No excuse.
