Recursion

This is a discussion on Recursion within the C Programming forums, part of the General Programming Boards category; Hello everyone. i got some homework i have no idea how to solve. so, if you can help me out ...

  1. #1
    Registered User
    Join Date
    Jun 2008
    Posts
    9

    Recursion

    Hello everyone.

    i got some homework i have no idea how to solve.
    so, if you can help me out a bit, that would be great.
    i'm not asking you to solve it for me, of course.

    ** No loops or pointers allowed.


    i need to write a function that gets 2 arrays of integers and their sizes and returns the amount of numbers repeating.
    for example:
    1,9,5,4
    5,10,18,1,3
    will return 2 (for 5 and 1);

    the declartaion:
    int intersect (const int arr1[],const in arr2[],int size1,int size2,....);

    (it's allowed to use more arguments in the function).

    Loops - Not allowed (for,do,while)
    side functions are allowed.
    every function that assists this one, must be recursive.
    assume the length of each array is 20 at most.

    guys, i don't even have a clue where to begin
    any kind of advice would be appritiated!

    Thanks!!
    Last edited by casper7; 07-12-2008 at 07:41 AM. Reason: disclaimer

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,849
    Recursion is a loop.

    First off, do you know how to solve the problem using normal loops?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Jun 2008
    Posts
    9
    i think that i do

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    You probably want to sort the two arrays, then compare them. Quick sort is a good recursive sort. Comparing them then becomes easy.
    Last edited by King Mir; 07-12-2008 at 10:53 AM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  5. #5
    Registered User
    Join Date
    Jun 2008
    Posts
    9
    thank you

    i don't know how qsort works ( i looked all over the net);
    any tips on how to write it on my own?

    and the only library i'm allowed to use is <stdio.h>;

    thanks again

  6. #6
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    A way to approach this problem more broadly is to identify known recursive algorithms that can be applied to the situation. Such algorithms include: accumulate/fold, which applies a function to total all the elements together in to one result; map/for each/transform, which applies a function to each element using; and filter/grep, which gets rid of all elements that do not satisfy a boolean condition function.

    For for example you can alternatively use this set of algorithms:
    For each element A in array one, filter list two on the condition of each element being equal to A.
    Then count the number of elements in the resultant list using accumulate (or more directly if you can figure out how).
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  7. #7
    Registered User
    Join Date
    Jun 2008
    Posts
    9
    what i did is:

    Code:
    int intersect(const int arr1[],const int arr2[], int size1,int size2)
    {
    	int static i,j,count;
    
    	if (i==size1){
    		i=0;
    		return 0;
    	}
    	
    	if (j==size2){
    		i++;
    		j=0;
    	}
    	if (arr1[i]==arr2[j])
    		count++;
    	j++;
    	intersect(arr1,arr2,size1,size2);
    	return count;
    }
    basicly, it runs threw arr2, and compares it to arr1[0],arr[1] ......, arr[size1]

    Now, the good news: it Works!
    the bad news are that if a number shows up more than once, it counts it again - something i don't want.

    my solution: (still an idea)
    sort both of the arrays, and then either eleminate repeating values, or ignore them in the fucntion itself.

    the thing is, im stuck at sorting using ***ONLY*** recursion (No loops, pointers allowed);

    thank you

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Qsort is another term for Quicksort. Quicksort is one of the best known of the fast, recursive algorithms. Also, the standard C library includes Qsort in stdlib.h iirc.

    As I understand your requirements however, you do not need Quicksort/Qsort, at all.

    Welcome to Bucketsort! It's usually not recursive, but can be written that way. This is the non-recursive (iterative) Bucketsort.

    Code:
    int Bucketsort(const int a[], int n, int bucket[20])   {
       int i;
       
       for(i = 0; i < n; i++)   {
          if(a[i] > 0)
             bucket[ a[i] ]++;
       }
    So if a[0] = 5, then bucket[5] is incremented by one. That is, bucket has a list in it's elements, of how many of each number, is found in a[].

    a[] = {1,2,3, 2}
    bucket[] == {0, 1, 2, 1} (There are no zero's, there is one 1, there are two 2's, and one 3).

    This solves your stated problem, except it's not recursive. Now, can you take out the for line, and give it a "base case", so it will not loop forever, and make it call itself?

    Give that a try. You will need to do this for both your arrays (so maybe bucketa[] and bucketb[]). That is, you'll need to bucketsort, both of your int arrays.

    Then recursively walk thru the two bucket arrays. Any element number greater than zero, in both arrays, is an intersecting number.

    Code:
    int check(int bucketa[], int bucketb[], int n, int i)   {
       if(++i >= n)
          return;
    
       if(bucketa[i] > 0 && bucketb[i] > 0)
          printf(" &#37;d,", i);
    
       check(int bucketa[], int bucketb[], int n, int i);   
    
    }
    The above is not tested, and is more for a springboard for your code, not working code.
    Last edited by Adak; 07-12-2008 at 03:57 PM.

  9. #9
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Quote Originally Posted by casper7 View Post
    what i did is:

    Code:
    int intersect(const int arr1[],const int arr2[], int size1,int size2)
    {
    	int static i,j,count;
    
    	if (i==size1){
    		i=0;
    		return 0;
    	}
    	
    	if (j==size2){
    		i++;
    		j=0;
    	}
    	if (arr1[i]==arr2[j])
    		count++;
    	j++;
    	intersect(arr1,arr2,size1,size2);
    	return count;
    }
    You cheated by using static variables. You don't need them. Just pass the variables as additional function parameters. And the return value should be the sum of all previous returns.

    But as you say you algorithm doesn't work. First decide what you want to do -- iteratively if you must. Then convert that into recursion. Or you can start right of by thinking recursively that means you need to define a relationship that does like this:

    Base cases - what happens when you have empty lists.
    Recursive case - how do you find result, given the result of a list that contains one less element.

    For you I recommend first finding an iterative solution. Between Adak and me, you have 3 algorithms that will work. pick one.
    Last edited by King Mir; 07-12-2008 at 07:58 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  10. #10
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Quote Originally Posted by casper7 View Post
    i don't know how qsort works ( i looked all over the net);
    any tips on how to write it on my own?
    http://www.google.com/search?q=recursive+quicksort

    first or second results.

    The only tricky part is writing a recursive partition function. But that isn't as hard as it sounds: it is just the use of the filter/grep algorithm, which is easy to write recursively.
    Last edited by King Mir; 07-12-2008 at 08:12 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  11. #11
    Registered User
    Join Date
    Jun 2008
    Posts
    9
    thank you for all of your replies.

    1. I am allowed to use static variables (i find it easier as well).
    2. i know how to solve this problem in an iterative way. the probs show up
    when i try to translate it into recursion.
    3. the kind of sorting i'm trying to do is finding the smallest number and
    returning its index. (function called placeOfMin(.......).
    then, using SortArray (funcition), i want to run threw the numbers and switching the first member with the smallest one. the parameters in sortArray are (int arr[50], int first, int size) whereas
    arr[] - is the array.
    first - is the first member of the array (that jumps by one everytime)
    size - the total amount of member in the array (an unput made by the user).

    the thing is i'm having a problem maiking it work.
    again, iteratively, i can do it in a minute...

    thank you very much, guys,....

    you are all upgrading my grade

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    If you use bucketsort, you'll find it easy, and everything will be "just right" for the comparisons from one array to the other.

    There is no sorting technique that is half as simple as bucketsort - a few lines only, inside the outermost loop (or in your case, recursive call).

    The reason bucketsort is so simple, is that it doesn't actually "sort", anything. It just represents the data in another array, in a different manner. In this case, in a very useful manner.

    It's easy to make a recursive sort function using loops, but it's not real easy to make that function without using any loops, imo.

  13. #13
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Quote Originally Posted by casper7 View Post
    3. the kind of sorting i'm trying to do is finding the smallest number and
    returning its index. (function called placeOfMin(.......).
    then, using SortArray (funcition), i want to run threw the numbers and switching the first member with the smallest one. the parameters in sortArray are (int arr[50], int first, int size) whereas
    arr[] - is the array.
    first - is the first member of the array (that jumps by one everytime)
    size - the total amount of member in the array (an unput made by the user).
    Ok. So you're looping twice. The inner loop finds the lowest element in the array. the outer loop just itterates by considering the minimum element of the array one index higher.

    Inner loop:
    Base case: the minimum of a one element list is that element
    Recursive step: the minimum of an element and a list of remaining elements. The minimum of the list of remaining elements is just a call to your minimum function (recursion). Comparing it to the present element with a < operation will tell you which is less.

    Now write that in C.

    See if you can write an outer loop algorithim on your own. Use the same approach: What is the base case? What partial solution do you split the list into so that you sort one element in each itteration?
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    If you're looking for a sorting algorithm that uses recursion and has no loops at all, then you could use Stooge sort, or Fib sort (both are shown on my website). Of course they're not great in terms of algorithmic complexity.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    It really isn't that hard to write selection sort recursively, which is what he's trying to do.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

Page 1 of 2 12 LastLast
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. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 10:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. 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
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM

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