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

Recursion is a loop.

First off, do you know how to solve the problem using normal loops?

i think that i do

You probably want to sort the two arrays, then compare them. Quick sort is a good recursive sort. Comparing them then becomes easy.

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

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).

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

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(" %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.

Quote:

---

Originally Posted by casper7

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.

Quote:

---

Originally Posted by casper7

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.

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

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.

Quote:

---

Originally Posted by casper7

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?

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.

It really isn't that hard to write selection sort recursively, which is what he's trying to do.