Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

across

Test your recursion skills. Given an integer array `a` of size `n`, write a recursive function with prototype ``` int findmin(int a[], int n); ``` that finds the minimum element of the array.

  • one year ago
  • one year ago

  • This Question is Open
  1. shadowfiend
    Best Response
    You've already chosen the best response.
    Medals 1

    If only there were a “spoilers” style so we could post code that was hidden unless highlighted ;)

    • one year ago
  2. across
    Best Response
    You've already chosen the best response.
    Medals 0

    I actually asked this question because I wanted to test a way to post code in OS. It turns out to be very cumbersome (or perhaps I'm missing an already-existing code tag somewhere?).

    • one year ago
  3. shadowfiend
    Best Response
    You've already chosen the best response.
    Medals 1

    @farmdawgnation was awesome a while back and added triple-backtick delimiting of code, Github-style. e.g.: ``` int findmin(int a[], int n) { if (n <= 0) return // uh-oh, dat bounds checking else if (n == 1) return // something? else { // what magic goeth here? } } ```

    • one year ago
  4. shadowfiend
    Best Response
    You've already chosen the best response.
    Medals 1

    You can use single backticks around something to mark it as inline code, or three on either side for blocks.

    • one year ago
  5. shadowfiend
    Best Response
    You've already chosen the best response.
    Medals 1

    And I think if you want to give the syntax highlighter a hint, you can put the language name after the three backticks, assuming it recognizes the language. Could be wrong about that part, I haven't used it too much :)

    • one year ago
  6. across
    Best Response
    You've already chosen the best response.
    Medals 0

    Oh, wow! That looks really nice.

    • one year ago
  7. shadowfiend
    Best Response
    You've already chosen the best response.
    Medals 1

    The puzzling question for me is, is there a way to make a tail-recursive min function… Ah-hah, I think I've figured that one out as well.

    • one year ago
  8. shadowfiend
    Best Response
    You've already chosen the best response.
    Medals 1

    Backticks have to be on their own line :) The live preview should be highlighting things for you as you go as well.

    • one year ago
  9. shadowfiend
    Best Response
    You've already chosen the best response.
    Medals 1

    The triple ones*

    • one year ago
  10. across
    Best Response
    You've already chosen the best response.
    Medals 0

    `test` ``` #include <iostream> using namespace std; int main() { return 0; } ```

    • one year ago
  11. across
    Best Response
    You've already chosen the best response.
    Medals 0

    You guys are awesome. ;)

    • one year ago
  12. shadowfiend
    Best Response
    You've already chosen the best response.
    Medals 1

    I'm just happy I got the tail recursive version. Boom!

    • one year ago
  13. across
    Best Response
    You've already chosen the best response.
    Medals 0

    Post it! This is the best tail-recursive version I could come up with: ``` int findmin(int a[], int n) { static int *min; if (min == 0) min = new int(a[n - 1]); else if (*min > a[n - 1]) *min = a[n - 1]; if (n == 1) return *min; else return findmin(a, n - 1); } ```

    • one year ago
  14. bdean20
    Best Response
    You've already chosen the best response.
    Medals 0

    I did this in python in a few different ways. http://pastebin.com/LZAkS8Ge btw, what markup code do you use to show code?

    • one year ago
  15. shadowfiend
    Best Response
    You've already chosen the best response.
    Medals 1

    Ew statics ;) Tail recursion is of course only really useful if the host language supports tail recursion optimizations. I used a helper function: ```cpp int findmin(int a[], int n) { if (n <= 0) return -1; // arbitrary “no minimum” value, not really a good idea else findmin(a[0], a[1..n - 1], n - 1); } int findmin(int lastmin, int a[], int n) { if (n <= 0) return lastmin; else { int currentmin = lastmin; if (a[0] < currentmin) currentmin = a[0]; findmin(currentmin, a[1..n - 1], n - 1); } } ``` You actually did a clever trick I'd forgotten about by using n as an index, avoiding copying the array. Solid goodness there, and here's an update of mine to do that: ```cpp int findmin(int a[], int n) { if (n <= 0) return -1; // arbitrary “no minimum” value, not really a good idea else return findmin(a[n - 1], a, n - 1); } int findmin(int lastmin, int a[], int n) { if (n <= 0) return lastmin; else { int currentmin = lastmin; if (a[n - 1] < currentmin) currentmin = a[n - 1]; return findmin(currentmin, a, n - 1); } } ``` Implemented in Scala: ```scala def findmin(a: List[Int]): Option[Int] = { a match { case first :: rest => findmin(first, rest) case _ => None // otherwise } } @scala.annotation.tailrec def findmin(currentMin: Int, a: List[Int]): Option[Int] = { a match { case first :: Nil if currentMin < first => Some(currentMin) case first :: Nil => Some(first) case first :: rest if currentMin < first => findmin(currentMin, rest) case first :: rest => findmin(first, rest) case _ => None } } ``` The upside of the above is that the `@scala.annotation.tailrec` asks the compiler to double-check that we're tail recursive (we are :p). The Scala compiler will automatically optimize tail recursion regardless of whether the annotation is present. I also think it reads better ;)

    • one year ago
  16. shadowfiend
    Best Response
    You've already chosen the best response.
    Medals 1

    Also worth mentioning about the Scala example above, the most basic collection in Scala is a List, which is a linked list. We're unpacking it in the match statements into the first part vs the rest of the List (much like Lisps let you via car/cdr or head/rest).

    • one year ago
  17. across
    Best Response
    You've already chosen the best response.
    Medals 0

    I see! I had forgotten how helpful helper functions (you don't say?) can be. Also, I don't think it can get any shorter than this C implementation a friend came up with: ``` int findmin(int a[], int n) { if (n == 1) return a[0]; n--; return f(a + (a[0] > a[n]), n); } ``` These guys are monsters. I feel so behind when it comes to programming. T_T

    • one year ago
  18. rsmith6559
    Best Response
    You've already chosen the best response.
    Medals 0

    Is this worth considering? #include <limits.h> int findmin( int a[], int n ) { int m; if( !n ) return( INT_MAX ); m = findmin( a, --n ); return( a[n] < m ? a[n] : m ); }

    • one year ago
  19. shadowfiend
    Best Response
    You've already chosen the best response.
    Medals 1

    Succinctness is not the only goal of programming. Indeed, it's often an anti-goal. @rsmith6559 my only problem with that one is that it seems to attend to edge cases but doesn't (what happens with a negative n?). And that it relies on INT_MAX, which always seems nasty even if technically correct. Then again, there's no good way to deal with a negative n or indeed any invalid entry.

    • one year ago
  20. rsmith6559
    Best Response
    You've already chosen the best response.
    Medals 0

    Dealing with a negative n isn't really the responsibility of this function. It should be validated by the calling code. INT_MAX would be the most likely value that would always be eliminated in the comparisons, and it's portable!

    • one year ago
  21. across
    Best Response
    You've already chosen the best response.
    Medals 0

    That's a good question: is it considered proper coding to implement error-handling procedures in functions, or to have the client file or whoever is using those functions validate the input passed?

    • one year ago
  22. rsmith6559
    Best Response
    You've already chosen the best response.
    Medals 0

    FWIW, in the cases of iteration or recursion, having the calling code handle validation will certainly execute faster. One check, instead of however many iterations checks. IMO, the answer is a very clear interface, and clear documentation/commenting. I don't see any issue, besides the speed, either way, but to be successful the implementer and client programmers need to be pretty much in lock step.

    • one year ago
  23. shadowfiend
    Best Response
    You've already chosen the best response.
    Medals 1

    Honestly, in the version with a helper, it's reasonable to only check at the entry point and take the check out of the helper. But in a language like C, where stuff like that is completely unsafe, it's rarely a good idea to eliminate the check altogether. In a language that carries length with the array, it's obviously a different matter. I agree that INT_MAX is perfectly valid. But the problem with it is that INT_MAX could actually be the minimum, so what does it mean if the function returns INT_MAX? Was there invalid information or was it the minimum value in the list? Most C functions seem to deal with this via a passed in pointer-to-an-error-flag of some sort. It's nasty, but it works.

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.