a small recursion function

This is a discussion on a small recursion function within the C Programming forums, part of the General Programming Boards category; howdy, This is my first recursion program... Need to write a function which returns the values of n/2, when gets ...

  1. #1
    Registered User
    Join Date
    Jun 2004
    Posts
    123

    a small recursion function

    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:
    Code:
    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??
    Last edited by ronenk; 11-07-2004 at 05:26 AM.

  2. #2
    not-a-geek
    Join Date
    Apr 2004
    Posts
    210
    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

    Code:
    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* :-)
    main() { int O[!0<<~-!0]; (!0<<!0)[O]+= ~0 +~(!0|!0<<!0); printf("a function calling "); }

  3. #3
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    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.

    Code:
    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);
    
    }

  4. #4
    Super Moderator Harbinger's Avatar
    Join Date
    Nov 2004
    Posts
    74
    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);

  5. #5
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    > this code does not work good but, demonstrate this idea.
    You should be doing
    return half(x);
    this doesn't work either:
    Code:
    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);
    	}
    }

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,602
    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."
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    I need to return the value of n, devided by 2; As an integer, not a float.
    is that better phrased?
    Last edited by ronenk; 11-07-2004 at 09:30 AM.

  8. #8
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    This is my solution to this problem:
    Code:
    #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));
    }

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,602
    Quote Originally Posted by ronenk
    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?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    It was drill to practice recursion.

  11. #11
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    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).
    Code:
    #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?

  12. #12
    Registered User
    Join Date
    Oct 2004
    Posts
    63
    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.

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    if( n < 2 )
         return 0;
    return 1 + half( n - 2 );
    Hm. At a glance, that should suffice.

    Quzah.
    Hope is the first step on the road to disappointment.

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  15. #15
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    Code:
    if( n < 2 )
    return 0;
    return 1 + half( n - 2 );
    thanx, quzah. this is good!

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-13-2011, 08:28 AM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  4. Replies: 3
    Last Post: 03-04-2005, 01:46 PM
  5. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21