Recursion

[Max]

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!

#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 ;
}

[Max]

Thanks Salem.....

[Max]

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!

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;
}

[Prelude]

>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:

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.

#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

[Prelude]

>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

[Max]

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??

#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;
}

[Prelude]

>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:

#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

[Max]

I don't want to use any loops anywhere in my program that is why I am replacing loops with recursions

[Prelude]

>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:

#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

[moi]

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.

[Nick]

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)

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.

[zahid]

"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?