Recursion

This is a discussion on Recursion within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Ive been trying to write a pseudo code function to recusively look for the smallest item in an array, but ...

  1. #1
    Microsoft. Who? MethodMan's Avatar
    Join Date
    Mar 2002
    Posts
    1,198

    Recursion

    Ive been trying to write a pseudo code function to recusively look for the smallest item in an array, but how do I set up a variable to hold the smallest element, without reseting it

    Smallset(A, j, k) // A = array, j - first element, k - last element
    {
    (test to see if empty)
    (if so exit)
    smallest = ? // dont know what to set this too
    if(k < smallest)
    k == smallest;
    else
    Smallest(A, j+1, k)

    return smallest
    }

    Didnt know where to post this.

    Do you see the problem, it will just clober it if I set it to 0.
    -MethodMan-

    Your Move:Life is a game, Play it; Life is a challenge, Meet it; Life is an opportunity, capture it.

    Homepage: http://www.freewebs.com/andy_moog/home.html

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Do you see the problem
    Have you tried using the smallest variable as a parameter to the recursive function?:
    Code:
    int find_min ( int *a, int min, int count )
    {
      if ( count > 0 ) {
        if ( *a < min )
          min = find_min ( a + 1, *a, count - 1 );
        else
          min = find_min ( a + 1, min, count - 1 );
      }
    
      return min;
    }
    It would be called like this with an array of 8 items:

    val = find_max ( array, array[0], 8 );

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

  3. #3
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    I general you can do something like
    #define NOT_FOUND INT_MAX
    has a sentinel.

    But in this case just
    stop the recursion when there's one element. Then
    that one elemen is the smallest. I think if I understand
    what you want to do is this
    Code:
    smallest(A, i, j)
        if (i >= j)
            return A[i]
        q = (i + j) / 2
        left = smallest(A, i, q)
        right = smallest(A, q + 1, j)
        if (A[left] <= A[right])
             return A[left]
        else 
             return A[right}
    }
    [edited by ygfperson for code tags]
    This solution is O(n) the same as doing it linearly.
    Last edited by Nick; 09-29-2002 at 11:38 PM.

  4. #4
    Seeking motivation... endo's Avatar
    Join Date
    May 2002
    Posts
    537
    Use code tags or Kermi3 will be after you!!!
    Couldn't think of anything interesting, cool or funny - sorry.

  5. #5
    Microsoft. Who? MethodMan's Avatar
    Join Date
    Mar 2002
    Posts
    1,198
    Thanks for the help, the code does its purpose. Just a few questions regarding the code.

    *a < min

    is that a reference to the first position in the array?

    find_min(a +1, *a, count -1)
    what does the a +1 do?

    *a points to the array again?

    and the count -1, goes down from the end by one?

    Thanks
    -MethodMan-

    Your Move:Life is a game, Play it; Life is a challenge, Meet it; Life is an opportunity, capture it.

    Homepage: http://www.freewebs.com/andy_moog/home.html

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >is that a reference to the first position in the array?
    a is a pointer, by dereferencing it you get the contents of the current element.

    >what does the a +1 do?
    a is a pointer , by recursing with the a + 1, you pass address of the next element in the array.

    >and the count -1, goes down from the end by one?
    Correct, this is so that the function knows when to stop.

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

  7. #7
    Microsoft. Who? MethodMan's Avatar
    Join Date
    Mar 2002
    Posts
    1,198
    Thanks for the clarifications
    Im doing a call trace, and I got to *a < min, what is min set to the first time it compares this?

    Is it just some piece of memory?
    -MethodMan-

    Your Move:Life is a game, Play it; Life is a challenge, Meet it; Life is an opportunity, capture it.

    Homepage: http://www.freewebs.com/andy_moog/home.html

  8. #8
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Use code tags or Kermi3 will be after you!!!
    Only for code that is in c++ and will run correctly.
    Since the code I gave is neither I suppose I don't
    have to use code tags.

    Here is some correct code
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    #define N 100
    
    int smallest(int A[], int i, int j)
    {
        int q;
        int left, right;
    
        if (i >= j)
            return A[i];
    
        q = (i + j)/2;
        left = smallest(A, i, q);
        right = smallest(A, q + 1, j);
        if (left < right)
            return left;
    
        return right;
    }
    
    int main(void)
    {
        int A[N];
        int i;
    
        srand(time(NULL));
        for (i = 0; i < N; ++i)
        {
            A[i] = rand() % N;
            printf("%3d ", A[i]);
            if ((i + 1) % 12 == 0)
                printf("\n");
        }
        printf("\n");
        printf("smallest = %d\n", smallest(A, 0, N - 1));
    
        return 0;
    }

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, 08:45 PM
  2. convert Recursion to linear can it be done
    By umen242 in forum C++ Programming
    Replies: 2
    Last Post: 10-15-2008, 02:58 AM
  3. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  4. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 09: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, 08:24 AM

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