Recursive function if statement mismatched types in Rust

Question

fn recursive_binary_search<T: Ord>(list: &mut [T], target: T) -> bool {
    if list.len() < 1 {
        return false;
    }
    let guess = list.len() / 2;
    if target == list[guess] {
        return true;
    } else if list[guess] > target {
        return recursive_binary_search(&mut list[0..guess], target);
    } else if list[guess] < target {
        return recursive_binary_search(&mut list[guess..list.len()], target);
    }
}

the compiler throws an error on if target == list[guess] saying

src/main.rs:33:5: 39:6 error: mismatched types [E0308]
src/main.rs:33     if target == list[guess] {
                   ^
src/main.rs:33:5: 39:6 help: run `rustc --explain E0308` to see a detailed explanation
src/main.rs:33:5: 39:6 note: expected type `bool`
src/main.rs:33:5: 39:6 note:    found type `()`
error: aborting due to previous error

I can't figure out how to rewrite this function to satisfy the type checker. I assume it is because I have the return type set to bool and there is a return function call?

Community · Accepted Answer · 2017-05-23 12:15:57Z

5

dikaiosune's answer explains the problem: the resulting type of your if is (), which is being returned instead of a bool.

Here's a few ways of writing the code a bit more idiomatically:

I'd start by writing it with implicit returns:

fn recursive_binary_search<T: Ord + Eq>(list: &[T], target: T) -> bool {
    if list.len() < 1 {
        return false;
    }

    let guess = list.len() / 2;

    if target == list[guess] {
        true
    } else if list[guess] > target {
        recursive_binary_search(&list[0..guess], target)
    } else {
        recursive_binary_search(&list[guess..list.len()], target)
    }
}

Then I'd perform the compare just once, instead of potentially twice. Could save a bit of time if comparisons are expensive, but it also looks nice with the match:

use std::cmp::Ordering;

fn recursive_binary_search<T: Ord + Eq>(list: &[T], target: T) -> bool {
    if list.is_empty() {
        return false;
    }

    let guess = list.len() / 2;

    match target.cmp(&list[guess]) {
        Ordering::Less    => recursive_binary_search(&list[..guess], target),
        Ordering::Greater => recursive_binary_search(&list[guess..], target),
        Ordering::Equal   => true,
    }
}

You can also drop the beginning and end parts of the ranges, and use is_empty for the guard clause.

Then there's the problem of the stack overflow if you search for a value larger than the biggest value... you need to ignore the pivot when recurring:

use std::cmp::Ordering;

fn recursive_binary_search<T: Ord>(list: &[T], target: T) -> bool {
    if list.is_empty() {
        return false;
    }

    let guess = list.len() / 2;

    match target.cmp(&list[guess]) {
        Ordering::Less    => recursive_binary_search(&list[..guess], target),
        Ordering::Greater => recursive_binary_search(&list[guess+1..], target),
        Ordering::Equal   => true,
    }
}

fn main() {
    assert!(!recursive_binary_search(&[1,2,3,4,5], 0));
    assert!(recursive_binary_search(&[1,2,3,4,5], 1));
    assert!(recursive_binary_search(&[1,2,3,4,5], 2));
    assert!(recursive_binary_search(&[1,2,3,4,5], 3));
    assert!(recursive_binary_search(&[1,2,3,4,5], 4));
    assert!(recursive_binary_search(&[1,2,3,4,5], 5));
    assert!(!recursive_binary_search(&[1,2,3,4,5], 6));
}

If you aren't implementing this for learning purposes, use the built-in binary_search.

edited May 23, 2017 at 12:15

CommunityBot

11 silver badge

answered May 31, 2016 at 20:12

Shepmaster

439k116 gold badges1.3k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

leshow Over a year ago

isn't the Eq trait unnecessary? Ord contains PartialOrd + Eq. and yes, of course this is just for learning purposes.

Shepmaster Over a year ago

@leshow yep; I copied that without thinking about it; removed in the last version that also fixes the infinite recursion bug.

leshow Over a year ago

thanks for the tip with match, that's a nice rust-y way of writing it.

dikaiosune · Accepted Answer · 2016-05-31 20:10:32Z

The issue here is that Rust evaluates the if/else if/else if block as the return value because it lacks an else clause, and statements which don't evaluate to any value have the type (). Incidentally, the code you've presented does exhaustively cover all possibilities (the item at the current index of the slice is either equal to, less than, or greater than the target), but the compiler doesn't know that unless you give it an else clause at the end:

fn recursive_binary_search<T: Ord + Eq>(list: &[T], target: T) -> bool {
    if list.len() < 1 {
        return false;
    }
    let guess = list.len() / 2;
    if target == list[guess] {
        return true;
    } else if list[guess] > target {
        return recursive_binary_search(&list[0..guess], target);
    } else {
        return recursive_binary_search(&list[guess..list.len()], target);
    }
}

PS: This function doesn't require mutable references, so I'd recommend using regular references as in my code above.

EDIT: For posterity, here's the same code w/o explicit returns:

fn recursive_binary_search<T: Ord>(list: &[T], target: T) -> bool {
    if list.len() < 1 {
        return false;
    }
    let guess = list.len() / 2;
    if target == list[guess] {
        true
    } else if list[guess] > target {
        recursive_binary_search(&list[0..guess], target)
    } else {
        recursive_binary_search(&list[guess..list.len()], target)
    }
}

Collectives™ on Stack Overflow

Recursive function if statement mismatched types in Rust

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related