Alternative way of thinking a [Recursion] algorithm to avoid stack overflow


#1

I am a beginner to Rust and experimenting. I found out I need to change the way I think to solve problems in Rust. As I expected Rust compiler threw stack overflow error but I don’t know how to change the algorithm. Anybody can point out, how to deal with such kind of algorithms.

I am building the algorithm presented in http://www.holdirdeinenvertrag.de/ with out modifications just to check how Rust works.

use std::collections::HashMap;
use std::collections::HashSet;

#[derive(Debug, PartialEq, Eq, Hash, Clone)]
struct Position{
    pub x : u32, 
    pub y : u32
}

impl Position {
    fn new(x : u32, y : u32) -> Position {
        Position {
            x,
            y
        }
    }

    fn inc_x(&mut self) {
        self.x += 1;
    }

    fn inc_y(&mut self) {
        self.x += 1;
    }

    fn dec_x(&mut self) {
        self.x -= 1;
    }

    fn dec_y(&mut self) {
        self.x -= 1;
    }
}

#[derive(Clone)]
struct Game {
    position: Position,
    letters: HashMap<Position, char>,
    obstacles: HashSet<Position>,
}

impl Game {
    fn is_invalid(player_position: &Position) -> bool {
        let (x , y) = (player_position.x, player_position.y);

        // Check whether player went out of boundary in 7x7 cell
        if x > 0 && x < 7 && y > 0 && y < 7 {
            return true;
        }
        false
    }
}

#[derive(Clone)]
struct GameProgress {
    visited: HashSet<Position>,
    collect: Vec<char>,
    game: Game
}

impl GameProgress {
    fn new(visited : HashSet<Position>, collect : Vec<char>, game : Game) -> GameProgress {
        GameProgress {
            visited,
            collect,
            game
        }
    }

    fn player_collected_all_letters(&self) -> bool {
        if self.collect.len() == self.game.letters.len() {
            return true;
        }

        false
    }
    fn mark_as_visited(&mut self, position : Position) {
        self.visited.insert(position);
    }

    fn add_to_player_letter_collection(&mut self, letter : char) {
        self.collect.push(letter);
    }

    fn move_player(&mut self, position : Position) {
        self.game.position = position;
    }

    fn player_position(&mut self) -> &Position {
        &self.game.position
    }

    fn get_all_letter_positions(&self) -> &HashMap<Position, char> {
        &self.game.letters
    }

    fn get_all_obstacle_positions(&self) -> &HashSet<Position> {
        &self.game.obstacles
    }

    fn has_visited(&self, position : &Position) -> bool {
        if self.visited.contains(position) {
            return true;
        }

        false
    }

    fn player_position_invalid(&self) -> bool {
        let (x , y) = (self.game.position.x, self.game.position.x);

        // Check whether player went out of boundary in 7x7 cell
        if x > 0 && x < 7 && y > 0 && y < 7 {
            return true;
        }
        false
    }

    fn is_obstacle(&self, player_position: &Position) -> bool {
        if self.game.obstacles.contains(player_position) {
            return true;
        }
        false
    }

    fn has_letter(&self, player_position: &Position) -> bool {
        if self.game.letters.contains_key(player_position) {
            return true
        }
        false
    }

    fn letter_at(&self, player_position: &Position) -> Option<&char> {
        self.game.letters.get(player_position)
    }

}



fn go_to(game_progress: &mut GameProgress) {
    let player = game_progress.clone();
    let player_position = player.game.position;

    while !game_progress.player_collected_all_letters() {
        // Check whether player goes out of boundary or visited the position
        if game_progress.player_position_invalid() &&
            game_progress.has_visited(&player_position) {
            return;
        }

       
        // current position contain letter then keep in players wallet
        if !game_progress.is_obstacle(&player_position) &&
            game_progress.has_letter(&player_position) {
                // let letter_at_position = game_progress.letter_at(&player_position);

                match game_progress.letter_at(&player_position).cloned() {
                    Some(character) => {
                        game_progress.add_to_player_letter_collection(character)
                    },
                    None => println!("Empty character at the position"),
                }     
        } 

        // Mark the position as visited
        game_progress.mark_as_visited(Position::new(player_position.x, player_position.y));
        
        {
           game_progress.game.position.inc_x();
           go_to(game_progress); 
        }

        {
            game_progress.game.position.inc_y();
            go_to(game_progress);
        }

        {
            game_progress.game.position.dec_x();
            go_to(game_progress);
        }

        {
            game_progress.game.position.dec_y();
            go_to(game_progress);
        }

    }


}

fn initialize_search(game: Game) {

    let mut game_progress = GameProgress {
        visited: HashSet::new(),
        collect: Vec::new(),
        game
    };

    go_to(&mut game_progress);

    print!("{:?}", game_progress.collect);
}

fn main() {
    let start_position = Position::new(6, 4);

    let mut letters: HashMap<Position, char> = HashMap::new();
    let mut obstacles: HashSet<Position> = HashSet::new();

    letters.insert(Position::new(2, 0), 'L');
    letters.insert(Position::new(3, 1), 'A');
    letters.insert(Position::new(4, 0), 'I');
    letters.insert(Position::new(2, 1), 'O');
    letters.insert(Position::new(5, 2), 'S');

    obstacles.insert(Position::new(0, 1));
    obstacles.insert(Position::new(0, 5));
    obstacles.insert(Position::new(1, 4));
    obstacles.insert(Position::new(2, 3));
    obstacles.insert(Position::new(2, 5));
    obstacles.insert(Position::new(6, 6));

    let game: Game = Game {
        position: start_position,
        letters,
        obstacles,
    };
    
    initialize_search(game);
}

#2

This got really long.

Anyways, turning recursive algorithms into iterative code is not difficult after you’ve done it a couple of times, but there is a lot to be said. So buckle up, it’s going to be a long ride!


First, some miscellaneous notes:

1. blocks don’t do that

{
    game_progress.game.position.inc_x();
    go_to(game_progress); 
}

This won’t do what you think it does. Exiting a block is not going to scope changes that you made to data visible outside the block. If you’re going to mutate a variable like this when descending down the stack, you’ll need to undo your changes as you ascend back up: (however, there’s a better alternative which we’ll get to later)

game_progress.game.position.inc_x();
go_to(game_progress); 
game_progress.game.position.dec_x();

2. Silly bool results

// please don't write this
fn has_visited(&self, position : &Position) -> bool {
    if self.visited.contains(position) {
        return true;
    }

    false
}

// write this instead
fn has_visited(&self, position : &Position) -> bool {
    self.visited.contains(position)
}

3. Check your logic

I won’t worth through the whole algorithm myself but there are definitely bugs here, e.g.

// Check whether player goes out of boundary or visited the position
if game_progress.player_position_invalid() &&
    game_progress.has_visited(&player_position) {
    return;
}

Okay. With those notes out of the way, lets get onto the good stuff.

When the stack’s too small, make your own stack on the heap

Don’t worry, it’s not complicated!

Think about it: what is a stack, really?

It’s a data structure with two operations:

  • You can push something new on top.
  • You can pop off the most recent thing.
  • also, you can probably check if it’s empty.

(Okay, so that’s three). Turns out rust already has a type like this: It’s called Vec. :wink:

Before we can do this, we need some preparation…

Separate the different kinds of state

We have three different kinds of state, grouped depending on how they change:

  1. Some state never changes, like letters and obstacles in Game
  2. Some state remembers all changes, like visited and collect in GameProgress
  3. Some state is like a function argument, like position in Game.

These three types of data should be passed differently.

  • Type 1 should be passed around immutably, probably as some &T.
  • Type 2 should be passed around mutably, probably as &mut T.
  • Type 3 should be passed by value and stored in a stack.

Let’s remove position from Game because Type 1 and Type 3 really don’t belong together.

// Type 1
#[derive(Clone)]
struct Game {
    letters: HashMap<Position, char>,
    obstacles: HashSet<Position>,
}

// Type 2
#[derive(Clone)]
struct GameProgress {
    visited: HashSet<Position>,
    collect: Vec<char>,
}

// Type 3
#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
struct Position {
    pub x: u32, 
    pub y: u32
}

Passing Position around by value

I said we should do this, right? Here’s how we can make that easier: Change the {inc,dec}_{x,y} methods so that they return a new position instead of modifying the current one.

impl Position {
    fn inc_x(self) -> Self {
        Position {
            x: self.x + 1,
            y: self.y,
        }
    }

    // ...etc...
}

This can be used to clean up the logic in go_to:

fn go_to(
    game: &Game,
    progress: &mut GameProgress,
    position: Position,
) {
    // logic for early returns, a.k.a. "base cases"
    if some_base_case() {
        return;
    }

    // ...
    // some logic here
    // ...
        
    go_to(game, progress, position.inc_x());
       
    go_to(game, progress, position.inc_y());
       
    go_to(game, progress, position.dec_x());
       
    go_to(game, progress, position.dec_y());

    // ...
    // Maybe some more logic here, who knows
    // ...
}

Using your own stack (maybe)

Alright! This is it! We’re really going to do it!

We’re going to take any arbitrary recursive function and make it iterative! Yeah!

We have a stack and a loop.

fn start_at(
    game: &Game,
    initial_position: Position,
) -> Solution
{
    // begin with the input on the stack
    let mut stack = vec![initial_position];

    let mut progress = { /* Initialize a GameProgress here */ };

    while let Some(position) = stack.pop() {
        // ... do stuff!
    }
}
  1. Each iteration of the loop is like entering the function.
  2. Every recursive call to a function should push the argument to the function (the new position) onto the stack before the call. (then we can continue)
  3. When the game has been won, you can use return to return the solution. (hence why I added a return type)
  4. When a recursive call returns due to a failure base case (e.g. “already visited”), all we need to do is continue without pushing anything. Since we popped a state at the beginning of the iteration, the next iteration will begin one level up.

Easy, right? Let’s do it!

fn start_at(
    game: &Game,
    initial_position: Position,
) -> Solution
{
    // begin with the input on the stack
    let mut stack = vec![initial_position];

    let mut progress = { /* Initialize a GameProgress here */ };

    while let Some(position) = stack.pop() {
        if we_won_the_game() {
            return the_solution();
        }

        if this_place_has_bad_coffee() {
            continue;
        }

        // ...
        // do things like mark the position visited
        // ...

        stack.push(position.inc_x());
        continue;

        stack.push(position.inc_y());
        continue;

        stack.push(position.dec_x());
        continue;

        stack.push(position.dec_y());
        continue;
    }
}

…yeah!

…uh oh, wait a second, this code is never going to work!! It will obviously never make past inc_x(), since it just unconditionally continues!

Oh no! Where did we go wrong!? :sob:


It turns out that we left out something fundamental in our design. You see, the stack isn’t just used to store function arguments and return values…

Stay tuned for part two, where we take into account… an iterator the instruction pointer!!
(it’s going to be an iterator)


#3

Part 2: The instruction pointer


First off, we can forget about the details of these guys:

#[derive(Debug, Copy, Clone, PartialEq, Eq)]
struct Position;
#[derive(Debug, Clone)]
struct Progress;
#[derive(Debug, Clone)]
struct Game;
#[derive(Debug, Clone)]
struct Solution;

impl Progress {
    fn new(game: &Game) -> Self                 { unimplemented!() }
    fn mark_visited(&mut self, pos: Position)   { unimplemented!() }
    fn is_visited(&self, pos: Position) -> bool { unimplemented!() }
    fn collect(&mut self, pos: Position)        { unimplemented!() }
    fn game_has_been_won(&self) -> bool         { unimplemented!() }
    fn solution(&self) -> Solution              { unimplemented!() }
}

The first question we ask ourselves is:

What are all the entry points to the function?

This generally includes the true entry point to the recursive function, as well each recursive call we can return from. Here’s our list:

// Possible entry points to the recursive function
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub enum Instruction {
    // the very beginning of the function
    JustGotHere,
    // we just got back from visiting pos.inc_x()
    WentRight,
    // etc...
    WentDown
    WentLeft,
    WentUp,
}

impl Instruction {
    pub fn first() -> Instruction { Instruction::JustGotHere }
}

This is the core thing we were missing to make the algorithm work By storing both the argument (Position) and an instruction pointer (Instruction) together on the stack, we can finally write the function.

Using your own stack (for reals this time)

Never mind what I wrote in the previous post; here’s how you really translate recursive code to use your stack:

  • At the beginning of each iteration, you pop off the top argument-instruction pair. This is like the function claiming ownership of its own data each time it is entered (from any entry point).
  • A failure base case simply continues.
  • A success base case can return or break from the loop.
  • A recursive call must put two pairs of data on the stack:
    • It must save its own state! (with an incremented instruction pointer so that it performs the next instruction when we return)
    • It must create a brand new pair for the call. (with a pointer to the first instruction).

Let’s try putting it in:

fn solve_the_puzzle(game: &Game, initial_position: Position) -> Solution
{
    use self::Instruction::*;

    let mut progress = Progress::new(game);
    let mut stack = vec![(initial_position, Instruction::first())];

    while let Some((pos, instruction)) = stack.pop() {
        match instruction {
            JustGotHere => {
                if progress.is_visited(pos) {
                    // continue without pushing anything to return to the "caller"
                    continue;
                }
                progress.mark_visited(pos);

                // ... other checks and stuff ...

                // recursive call to go right:
                stack.push((pos, WentRight));
                stack.push((pos.inc_x(), Instruction::first()));
            },

            WentRight => {
                // recursive call to go down:
                stack.push((pos, WentDown));
                stack.push((pos.inc_y(), Instruction::first()));
            },

            WentDown => {
                // recursive call to go down:
                stack.push((pos, WentLeft));
                stack.push((pos.dec_x(), Instruction::first()));
            },

            WentLeft => {
                // recursive call to go up:
                stack.push((pos, WentUp));
                stack.push((pos.dec_y(), Instruction::first()));
            },

            WentUp => {}, // continue without pushing anything to return to the "caller"
        }
    }
}

Awww geez awww man awww geez that looks repetitive :frowning:

Yeah sorta. It’s very easy to make mistakes, too. This isn’t the kind of code anybody should want to be writing.

There’s a whole world of possible solutions to this, and everyone probably has their own favorite. My favorite solution involves iterators. This technique isn’t always something you can do, but it’s definitely something you can do in simple cases such as these.

(more generally, it works on any depth-first traversal such as Oedipus’ path in the problem)

A simple stream of Actions

What are all of the unique things that happen in the algorithm?

  • When we first arrive somewhere, we do some bookkeeping (checking if the tile is an obstacle, etc).
  • Aside from that, it’s just recursive calls.

Let’s make a type describing each of the things we can do:

#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub enum Action {
    DoSomeBookkeeping,
    GoThatWay(Position),
}

After that, my trick is this: Use an Iterator<Item=Action> as your “instruction pointer.”

Why? Because it automatically handles half of the logic for you.

fn solve_the_puzzle(game: &Game, initial_position: Position) -> Solution
{
    let mut progress = Progress::new(game);

    // Have a helper function for generating new entries in the stack.
    let new_recursive_call = |pos: Position| {
        // in our case, there's a fixed set of actions;
        let actions = vec![
            Action::DoSomeBookkeeping,
            Action::GoThatWay(pos.inc_x()),
            Action::GoThatWay(pos.inc_y()),
            Action::GoThatWay(pos.dec_x()),
            Action::GoThatWay(pos.dec_y()),
        ];
        // The stack will store the function argument,
        //  and an iterator of remaining actions.
        (pos, actions.into_iter())
    };

    let mut stack = vec![new_recursive_call(initial_position)];

    // Look at the bottom of the callstack
    while let Some((pos, mut remaining_actions)) = stack.pop() {

        // Read actions one at a time, advancing the iterator.
        // This loop may be interrupted partway through by a recursive
        //   call, but it'll pick up where it left off when it gets back.
        // When this loop ends, nothing will be placed back onto the stack,
        //   so that we go back up one level in the callstack.
        while let Some(action) = remaining_actions.next() {

            match action {
                Action::DoSomeBookkeeping => {
                    if progress.is_visited(pos) {
                        // finish a recursive call
                        continue;
                    }
                    progress.mark_visited(pos);

                    // ... other stuff ...

                    // If we fall off the end here with nothing happening,
                    // the 'while let Some(action)' loop will continue
                    // with the next action.
                },

                Action::GoThatWay(new_pos) => {
                    // Save our state.
                    // No need to "increment the instruction pointer";
                    //  since it is an iterator, it effectively incremented
                    //  itself when we read it.
                    stack.push((pos, remaining_actions));
                    // And now prepare the recursive call.
                    stack.push(new_recursive_call(new_pos));
                    continue;
                },
            }
        }
    }
}

Your turn :muscle:

None of my code is a complete working sample so there’s plenty for you to do. Hopefully this has given you some ideas.