Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

across

  • 3 years ago

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.

  • This Question is Open
  1. shadowfiend
    • 3 years ago
    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 ;)

  2. across
    • 3 years ago
    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?).

  3. shadowfiend
    • 3 years ago
    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? } } ```

  4. shadowfiend
    • 3 years ago
    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.

  5. shadowfiend
    • 3 years ago
    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 :)

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

    Oh, wow! That looks really nice.

  7. shadowfiend
    • 3 years ago
    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.

  8. shadowfiend
    • 3 years ago
    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.

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

    The triple ones*

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

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

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

    You guys are awesome. ;)

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

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

  13. across
    • 3 years ago
    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); } ```

  14. bdean20
    • 3 years ago
    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?

  15. shadowfiend
    • 3 years ago
    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 ;)

  16. shadowfiend
    • 3 years ago
    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).

  17. across
    • 3 years ago
    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

  18. rsmith6559
    • 3 years ago
    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 ); }

  19. shadowfiend
    • 3 years ago
    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.

  20. rsmith6559
    • 3 years ago
    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!

  21. across
    • 3 years ago
    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?

  22. rsmith6559
    • 3 years ago
    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.

  23. shadowfiend
    • 3 years ago
    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.

  24. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy