[SOLVED] Error with Tail Recursion

help
1

I've started learning Rust a couple of days ago, so, please bear with me.
I wanted to write a recursive function to calculate a Fibonacci number:

use std::collections::VecDeque;
use tailcall::tailcall;
#[tailcall]
fn fib(n: i32) -> i32 {
    fn fib_aux(x: i32, series: VecDeque<i32>, sum: i32, counter: i32) -> i32 {
        match x {
            0 => 0,
            1 => 1,
            counter => sum,
            _ => fib_aux(
                x,
                series.push_front(sum),
                sum + series[0],
                counter + 1,
            ),
        }
    }
    fib_aux(n, VecDeque::from([1]), 1, 2)
}

But when I compile it I get the following message:

Compiling playground v0.0.1 (/playground)
error[E0308]: mismatched types
  --> src/lib.rs:14:17
   |
14 |                 series.push_front(sum),
   |                 ^^^^^^^^^^^^^^^^^^^^^^ expected struct `VecDeque`, found `()`
   |
   = note: expected struct `VecDeque<i32>`
           found unit type `()`
note: method `push_front` modifies its receiver in-place
  --> src/lib.rs:14:24
   |
14 |                 series.push_front(sum),
   |                 ------ ^^^^^^^^^^ this call modifies `series` in-place
   |                 |
   |                 you probably want to use this value after calling the method...
   = note: ...instead of the `()` output of method `push_front`

For more information about this error, try `rustc --explain E0308`.
error: could not compile `playground` due to previous error

Looking at the docs I see that push_front method doesn't return a new VecDeque, but it's just a procedure.
So, my question is, I could pass a new VecDeque with the value sum pre-pended to the original one?

2

The required change to the relevant part is

(In addition, you have to declare series as mut series: VecDeque<i32>, of course.)

1 Like
3

In addition, the fib_aux here is not a recursive function as its 3rd arm counter => sum is a never-fail case. The left side of theatch arm is pattern, not an expression. That's why warning: unreachable pattern appears on build.

2 Likes
4

#EDITED#
Thank you guys for your prompt replies.
So, I modified the function as follows:

use std::collections::VecDeque;
use tailcall::tailcall;
#[tailcall]
fn fib(n: i32) -> i32 {
    fn fib_aux(x: i32, mut series: VecDeque<i32>, sum: i32, counter: i32) -> i32 {
        if x == 0 {
            0
        } else if x == 1 {
            1
        } else if x == counter {
            sum
        } else {
            series.push_front(sum);
            fib_aux(x, series, sum + series[0], counter + 1)
        }
    }
    fib_aux(n, VecDeque::from([1]), 1, 2)
}

and this is what I get when I build it:

error[E0382]: borrow of moved value: `series`
  --> src/main.rs:34:38
   |
25 |     fn fib_aux(x: i32, mut series: VecDeque<i32>, sum: i32, counter: i32) -> i32 {
   |                        ---------- move occurs because `series` has type `VecDeque<i32>`, which does not implement the `Copy` trait
...
34 |             fib_aux(x, series, sum + series[0], counter + 1)
   |                        ------        ^^^^^^ value borrowed here after move
   |                        |
   |                        value moved here

For more information about this error, try `rustc --explain E0382`.

I'm a little lost, since, coming from Scala, I'm not very proficient with the concept of Ownership (yet?).

5

You pass series to the function, but you are also trying to re-use it for indexing (series[0]). You have to perform the addition first, and only then, when you don't need the series anymore, can you pass it to the function by value.

2 Likes
6

Alright! So if I write:

fn main() {
    println!("F₁₀  = {:?}", fib(10));
}

use std::collections::VecDeque;
use tailcall::tailcall;
#[tailcall]
fn fib(n: i32) -> i32 {
    fn fib_aux(x: i32,mut series: VecDeque<i32>, sum: i32, counter: i32) -> i32 {
        let mut new_sum = 0;
        if x == 0 {
            0
        } else if x == 1 {
            1
        } else if x == counter {
            sum
        } else {
            new_sum = sum + series[0];
            series.push_front(sum);
            fib_aux(x, series, new_sum, counter + 1)
        }
    }
    fib_aux(n, VecDeque::from([1]), 1, 2)
}

It works! Although, I must say, this way defeats the purpose of writing a recursive function; i.e. avoiding mutable variables.
But thank you very much for the help.
Have a good one.

7

Avoiding mutability is not the purpose of recursion.

2 Likes
8

Note that your implementation requires O(𝓃) memory as series will always contain the entire sequence. An alternative (iterative) approach would be something like this:

fn main() {
    println!("F₁₀  = {:?}", fib().nth(10).unwrap());
}

fn fib() -> impl Iterator<Item=i32> {
    let mut x: i32 = 0;
    let mut y: i32 = 1;
    std::iter::from_fn(move || Some({
        let z = x + y;
        let out = x;
        x = y;
        y = z;
        out
    }))
}

Edit: With a helper function, you can write something similar in a more tail-recursive style:

fn main() {
    println!("F₁₀  = {:?}", fib().nth(10).unwrap());
}

fn fib() -> impl Iterator<Item = i32> {
    trampoline_iter((0, 1), |(x, y)| Some((x, (y, x + y))))
}

fn trampoline_iter<F, St, Out>(init: St, f: F) -> impl Iterator<Item = Out>
where
    F: Fn(St) -> Option<(Out, St)>,
{
    let mut state = Some(init);
    std::iter::from_fn(move || match f(state.take().unwrap()) {
        None => None,
        Some((o, st)) => {
            state = Some(st);
            Some(o)
        }
    })
}

Edit 2: std::iter::successors can take the place of trampoline_iter:

fn main() {
    println!("F₁₀  = {:?}", fib().nth(10).unwrap());
}

fn fib() -> impl Iterator<Item = i32> {
    std::iter::successors(Some((0, 1)), |&(x, y)| Some((y, x + y))).map(|(x, _)| x)
}
5 Likes
9

Hey, it's the first thing that occurred to me when successors was stabilized! You can used checked_add to terminate the iterator when it would have otherwised overflowed.

use core::iter::successors;
type Tuple = (u128, u128);

fn main() {
    let start: Tuple = (0, 1);
    let fct = |&(a, b): &Tuple| b.checked_mul(a+1).map(|c| (a+1, c));
    let fib = |&(a, b): &Tuple| a.checked_add(b  ).map(|c| (b,   c));

    successors(Some(start), fct).map(|t| t.1).for_each(|f| println!("{}", f));
    successors(Some(start), fib).map(|t| t.1).for_each(|f| println!("{}", f));
}
2 Likes
10

Wow!!! Thank you man, but as I said, I've started Rust a couple of days ago, so all this looks advanced to me. But I'm gonna save it for further reference, hoping to catch up with this level of proficiency.
Yet your comment made me think and I found out that for some contorted reason I was actually building also a Fibonacci sequence which I don't need.
So I rewrote the function as follows:

use tailcall::tailcall;
fn main() {
    // println!("u128 max value is {}", u128::max_value());
    println!("Fn = {}", fib(180));
}

#[tailcall]
fn fib(n: u32) -> u128 {
    fn fib_aux(x:u32, prev: u128,  curr: u128, counter: u32) -> u128 {
        if x > 186 {
            println!("INTEGER OVERFLOW!!!");
            0
        } else if x == 0 {
            0
        } else if x == 1 {
            1
        } else if x == counter {
            curr
        } else {
            fib_aux(x, curr, prev + curr, counter + 1)
        }
    }
    fib_aux(n, 1, 1, 2)
}

Edit 1 Just getting rid of unnecessary lines:

#[tailcall]
fn fib(n: u32) -> u128 {
    fn fib_aux(x: u32, prev: u128, curr: u128, counter: u32) -> u128 {
        match x {
            y if y == 0 => 0,
            y if y == counter => curr,
            _ => fib_aux(x, curr, prev + curr, counter + 1),
        }
    }
    match n {
        num if num > 186 => {
            println!("INTEGER OVERFLOW!!!");
            0
        }
        _ => fib_aux(n, 0, 1, 1),
    }
}

End of edit
What do you think?

Actually is there a Require function forcing to use only certain values (say denominator > 0 in a fraction)?

11

I would usually write this match like this:

    match n {
        187.. => panic!("INTEGER OVERFLOW!!!"),
        _ => fib_aux(n, 0, 1, 1),
    }

Instead of binding a variable for comparison, it uses a range pattern (187..) to match numbers in the range [187, ∞). Also, panic! will terminate the program instead of returning an incorrect value from the function.

1 Like
12

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.