a small recursion function

[ronenk]

howdy,
This is my first recursion program...
Need to write a function which returns the values of n/2, when gets the valuue of n. this is what I wrote:

int half (int n)
{
	int x,y;
	if (n==0)
		return 0;
	x = n-2;
	y = n-x;
	if (y >= x)
		return (y);
	else
	{
		half(x);
		
	}
     return (y);
}

Somehow recursion doesn't ever happen. Debugger shows the function enters the 'else', but doesn't commit the half(x);
Why??

[Nyda]

For a start, are you sure you really want to discard the return value of half(x); in your else block? You could also add something like this

printf("> n:%d, x:%d, y:%d\n", n, x, y);

(requires you to also include stdio.h) between y = n-x; and if (y >= x) to see if your y is really behaving the way you expect it to do *hint* :-)

[ronenk]

I think there has to be a way to keep the original value of n, so I have a reference, each time function runs, & I can calculate with third variable the value I need.
this code does not work good but, demonstrate this idea.
please comment.

int half (int n)
{
	int static y;
	int x,w;
	y=n;
	if (n==0)
		return 0;
	x = n-1;
	w = y-x;
	if (w >= x)
	{
		return (w);
	
	}
	else
	{
		half(x);
	}
		return (w);

}

[Harbinger]

http://c2.com/cgi/wiki?TailCallOptimization
Recursion is just a disguised loop.
Simple recursive functions, especially those where the recursive step is the last thing to be done, can often be reduced by the compiler to a loop.

> this code does not work good but, demonstrate this idea.
You should be doing
return half(x);

[ronenk]

> this code does not work good but, demonstrate this idea.
You should be doing
return half(x);

this doesn't work either:

int half (int n)
{
	int static y;
	int x,w;
	y=n;
	if (n==0)
		return 0;
	x = n-1;
	w = y-x;
	if (w >= x)
	{
		return (w);
	
	}
	else
	{
	return half(x);
	}
}

[laserlight]

hmm... what exactly are you trying to do?
I dont understand "Need to write a function which returns the values of n/2, when gets the valuue of n."

[ronenk]

I need to return the value of n, devided by 2; As an integer, not a float.
is that better phrased?

[ronenk]

This is my solution to this problem:

#include<stdio.h>


int half (int n, int y)
{
	int x,w;
	if (n==0)
		return 0;
	x = n-1;
	w = y-x;
	if (w >= x)
		return (w);
	
	else
		return half(x, y);
}

int main (void)
{
	int y;
	int n=29;
	y=n;
	printf  ("half of %d is %d\n",n , half(n, y));
}

[laserlight]

I need to return the value of n, devided by 2; As an integer, not a float.
is that better phrased?

In that case, why in the world do you need recursion?

Wouldnt a simple return n/2; work?

[ronenk]

It was drill to practice recursion.

[ronenk]

My teacher saw this function & said it can be done more efficiently, with no local variable.
This supposes to be the general template:

[code]
int half (int n)
{
if (n<=???)
return ???;
return (????? half(n, y));
}

The best I could do is eliminating one local veritable.
Still, I'm left with one superfluous local variable (w) & superfluous parameter variable (y).

#include<stdio.h>


int half (int n, int y)
{
	int w;
	if (n<=1)
		return 1;
	n--;
	w = y-n;
	if (w >= n)
		return (w);
	
	else
		return half(n, y);
}

int main (void)
{
	int y;
	int n=8;
	y=n;
	printf  ("half of %d is %d\n",n , half(n, y));
}

Any idea to change the concept of calculation here?

[Philandrew]

If you want to practise recursion...I'd use something more applicable. My C++ book used the following idea to illustrate it:

Fibonacci Sequence goes like 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, etc
each number is equal to the number before it plus the number before that (1+2=3, 2+3=5, 3+5=8, etc)
Take in a number, and output its fibonacci value
input:
5
output:
x is the 5th fibonacci number

hint: f(n-1) + f(n-2) [or something like it] should be used.

I don't think doing n/2 helps anybody understand recursion becauses recursion doesn't really apply to it.

[quzah]

if( n < 2 )
     return 0;
return 1 + half( n - 2 );

Hm. At a glance, that should suffice.

Quzah.

[quzah]

If you want to practise recursion...I'd use something more applicable.

It's homework. It doesn't have to be "applicable", or even logical. Just something drummed up for them to do by the instructor.

Quzah.

[ronenk]

Code:
if( n < 2 )
return 0;
return 1 + half( n - 2 );

thanx, quzah. this is good!