Recursion

This is a discussion on Recursion within the C Programming forums, part of the General Programming Boards category; I am trying to use a recursion instead of a loop to calculate the sum of squares of n. n ...

  1. #1
    Max
    Max is offline
    Registered User Max's Avatar
    Join Date
    Jul 2002
    Posts
    110

    Recursion

    I am trying to use a recursion instead of a loop to calculate the sum of squares of n. n is a number 1 to 100 that the user enters.

    Here is my program so far but I think I messed it up... can't make it to work.......help!

    Code:
    #include <stdio.h>
    
    void recursion(int k, long n);
    int main(void)
    {
    	long n,sum;
    
    	printf("Enter n: ");
    	scanf("%ld", &n);
    	printf("You entered: n= %ld\n",n);
    
    	if (n>100)
    	{
             printf("squares n is larger than 100\n");
    	     return 1;
    	}
    	recursion(1,n);
    
    	printf("sum=%ld\n",sum);
    
    return 0;
    }
    void recursion(int k,long n)
    {
    	long sum=0;
    	
    	if (k<=n)
    		recursion(sum+=k*k,0);
    	                     	
        return ;
    }

  2. #2
    Max
    Max is offline
    Registered User Max's Avatar
    Join Date
    Jul 2002
    Posts
    110
    Thanks Salem.....

  3. #3
    Max
    Max is offline
    Registered User Max's Avatar
    Join Date
    Jul 2002
    Posts
    110
    here is another program where I am trying to to change to while loop into a recursion. I am trying to print a Fobannicci sequence

    ex: 0,1,1,2,3,5,8,13.....

    Any suggestions...because I am stuck!

    Code:
    long recursion(long k);
    int main(int argc, char*argv[]) 
    {
      int n,k,f0,f1,f2;
      
      if (argc==2) n=atoi(argv[1]);
      else
      {
    	  perror("fib"); exit(1);
      }
    
      f0 = f1 = 1; 
      k=0;
      printf("%2d %3d\n", 0, f0);              
      printf("%2d %3d\n", 1, f1);
    
      printf("%2d %3d\n", k++, recursion(n));
    
     return 0;
    }
    
    long recursion(long n)
    {
      int f0,f1,f2;
      int k=2;
      while (k<=n)
      {
    	  f2 = f0 + f1;
    	  
    	  f0 = f1;                               
          f1 = f2;
      }
      return f2;
    }

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I am trying to print a Fobannicci sequence
    This is one of the recursive implementations that you need to be very careful writing or it will be incredibly inefficient. This is the icky version, it's simple, but horrible when it comes to execution time and stack depth:
    Code:
    unsigned long fib ( int n )
    {
      if ( n == 0 )
        return 0;
      else if ( n == 1 )
        return 1;
      else
        return fib ( n - 1 ) + fib ( n - 2 );
    }
    And the same function more carefully designed to save the values so that they don't have to be recalculated. You'll notice that it is considerably faster and actually finishes in a reasonable amount of time.
    Code:
    #include <stdio.h>
    
    static int preset[47];
    
    unsigned long fib ( int n )
    {
      int t;
    
      if ( preset[n] != 0 )
        return preset[n];
      else if ( n == 0 )
        t = 0;
      else if ( n == 1 )
        t = 1;
      else if ( n > 1 )
        t = fib ( n - 1 ) + fib ( n - 2 );
    
      return preset[n] = t;
    }
    
    int main ( void )
    {
      int i;
    
      for ( i = 0; i < 47; i++ )
        printf ( "%lu\n", fib ( i ) );
    
      return 0;
    }
    -Prelude
    My best code is written with the delete key.

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >On second thoughts, this thread probably explains recursion much better
    Hehe, I'm flattered Salem.

    p.s. It's about 15 minutes after my last post and the icky version is still running. I was not joking when I said it was bad.

    -Prelude
    My best code is written with the delete key.

  6. #6
    Max
    Max is offline
    Registered User Max's Avatar
    Join Date
    Jul 2002
    Posts
    110
    Well I get my Fibonacci program working but it displays only the vfirst two value and the example if I want 10
    the program displays 0,1,55

    I want to be able to display all numbers up to 55 such as:
    0,1,2,3,5,8,13,21,34,55

    Cant get it to work...any suggestions??

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    long recursion(long i);
    int main(int argc, char*argv[]) 
    {
      int n,k,f0,f1,f2;
      
      if (argc==2) n=atoi(argv[1]);
      else
      {
    	  perror("fib"); exit(1);
      }
    
      f0 = f1 = 1; 
      k=0;
      printf("%2d %3d\n", 0, f0);              
      printf("%2d %3d\n", 1, f1);
    
      printf("%2d %3d\n", k++, recursion(n));
    
     return 0;
    }
    
    long recursion(long n)
    {
     	  if (n>2) 
    	         return recursion(n-2) + recursion(n-1);
    	  else
    		  return 1;
    }

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I want to be able to display all numbers up to 55
    Loop with i from 1 to n with i as the argument to recursion. That will print all of the values from 1 to n:
    Code:
    #include <stdio.h>
    
    long fib ( int n )
    {
      if ( n > 2 )
        return fib ( n - 1 ) + fib ( n - 2 );
      else
        return 1;
    }
    
    int main ( void )
    {
      int i;
    
      for ( i = 1; i < 11; i++ )
        printf ( "%ld\n", fib ( i ) );
    
      return 0;
    }
    And you should seriously consider using strtol instead of atoi, it handles errors with less chaos, death, and destruction.

    -Prelude
    My best code is written with the delete key.

  8. #8
    Max
    Max is offline
    Registered User Max's Avatar
    Join Date
    Jul 2002
    Posts
    110
    I don't want to use any loops anywhere in my program that is why I am replacing loops with recursions

  9. #9
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I don't want to use any loops anywhere in my program that is why I am replacing loops with recursions
    That's silly, but you can write a recursive print function that prints the numbers:
    Code:
    #include <stdio.h>
    
    long fib ( int n )
    {
      if ( n > 2 )
        return fib ( n - 1 ) + fib ( n - 2 );
      else
        return 1;
    }
    
    void print_fib ( int n )
    {
      if ( n > 1 )
        print_fib ( n - 1 );
    
      printf ( "%ld\n", fib ( n ) );
    }
    
    int main ( void )
    {
      print_fib ( 10 );
    
      return 0;
    }
    -Prelude
    My best code is written with the delete key.

  10. #10
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    Originally posted by Max
    I don't want to use any loops anywhere in my program that is why I am replacing loops with recursions
    are you sure about this? i mean for someone with a limited grasp of recursion you seem to like it a lot. the recursive solution prelude just posted is slower, harder to read, and harder to maintain and debug than a simple loop. i'm just curious as to where you are coming from.
    hello, internet!

  11. #11
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    i'm just curious as to where you are coming from.
    From a class room; it's a popular exercise. Loops are really
    structured gotos and tail recursion is gotos with parameters.
    There's been a lot of fib problems lately but anyways.

    Take (untested)

    Code:
    int fib(int n)
    {
         int p = 0, q = 1;
         int i, t;
    
         for (i = 0; i < n; ++i)
         {
               t = q;
               q = p + q;
               p = t;
          }
    
           return p;
    }
    
    int fib_recur(int p, int q, i)
    {
         if (i == 0)
               return p;
         else
               return fib_recur(q, p + q, i - 1);
    } 
    
    int fr(int n)
    {
         return fib_recur(0, 1, n);
    }
    The state variables i, p, q are parameters and the
    while loop is turned into a goto.

  12. #12
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    532
    "Tower of Hanoi" is an unique example of perfect problem to solve using recursion.

    So, I will advice Max to read, understand and study the problem again and again untill the concept is transparent. This study will help to solve problem or think recursion in future in another case.
    I found no appropriate example of recursion like this one.

    Anyone of you have stock of problems like this?
    Last edited by zahid; 10-10-2002 at 12:44 AM.
    [ Never code before desk work ]
    -------------------------------------:-->
    A man who fears Nothing is the man who Loves Nothing
    If you Love Nothing, what joy is there in your life.
    =------------------------------------------------------= - I may be wrong.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. convert Recursion to linear can it be done
    By umen242 in forum C++ Programming
    Replies: 2
    Last Post: 10-15-2008, 03:58 AM
  3. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 10:37 AM
  4. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  5. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM

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