I was doing AoC24 in Rust, when apparently found something strange about recursion in Rust.
The test file is just:
125 17
The program is:
use std::io::Read;
use std::fs::File;
const TURNS: i32 = 75;
fn main() {
let mut file = File::open("./test.txt").unwrap();
let mut text = String::new();
file.read_to_string(&mut text).unwrap();
let stones: Vec<i64> = text.split_whitespace().filter(|s| !s.is_empty()).map(|s| s.parse::<i64>().unwrap()).collect::<Vec<i64>>();
let mut total = 0;
fn apply_rules(stone: i64, blink: i32, total: i64) -> i64 {
if blink == 0 {
return total;
}
if stone == 0 {
return apply_rules(1, blink - 1, total);
}
let s = stone.to_string();
let l = s.len();
if l % 2 == 0 {
let first = s[0..l/2].to_owned();
let second = s[l/2..].to_owned();
let mut t = total;
// infinite recursion happens here
t += apply_rules(first.parse::<i64>().unwrap(), blink-1, 1);
t += apply_rules(second.parse::<i64>().unwrap(), blink-1, 1);
return t;
}
return apply_rules(stone*2024, blink-1, total);
}
for stone in stones {
total += apply_rules(stone, TURNS, 1);
}
println!("Total: {}", total);
}
If you comment out either one of the recursive functions below the comment, the program will complete, otherwise, will recurse infinitely. Just happens with these two. I feel like I'm missing something, because the first should recurse, then the second, without them being related at all, but they strangely are.
If TURNS=25, I get 56520 calls to the function with both functions uncommented.
With TURNS=75 I cannot tell, because the program doesn't exit.
If I comment one of them off, I will only get 41 calls, for each.
So, to summarize, with TURNS=25 I get 56520 calls for both and 41 calls if one of them is commented.
85685 for both, and 27 for one function, which makes even less sense.
EDIT: I made a mistake. It is 244362 and 54. Sorry
This is the code I'm using to count function calls:
use std::io::Read;
use std::fs::File;
const TURNS: i32 = 26;
fn main() {
let mut file = File::open("./test.txt").unwrap();
let mut text = String::new();
file.read_to_string(&mut text).unwrap();
let stones: Vec<i64> = text.split_whitespace().filter(|s| !s.is_empty()).map(|s| s.parse::<i64>().unwrap()).collect::<Vec<i64>>();
let mut total = 0;
let mut a = 0;
fn apply_rules(stone: i64, blink: i32, total: i64, a: &mut i32) -> i64 {
*a += 1;
if blink == 0 {
return total;
}
if stone == 0 {
return apply_rules(1, blink - 1, total, a);
}
let s = stone.to_string();
let l = s.len();
if l % 2 == 0 {
let first = s[0..l/2].to_owned();
let second = s[l/2..].to_owned();
let mut t = total;
t += apply_rules(first.parse::<i64>().unwrap(), blink-1, 1, a);
t += apply_rules(second.parse::<i64>().unwrap(), blink-1, 1,a);
return t;
}
return apply_rules(stone*2024, blink-1, total,a);
}
for stone in stones {
total += apply_rules(stone, TURNS, 1, &mut a);
}
println!("Calls: {}", a);
println!("Total: {}", total);
}
I would suggest sitting down and working out by hand how the number of calls scales with the value of TURNS in the worst case (i.e. when l%2 == 0 at every call).
Sorry I made a mistake. The numbers are 244362 for both and 54 for a single one.
My confusion comes from the fact that there is never a stack overflow, that I would understand.
I will try to make a simple one by hand.
I did 2-3 years of previous years (full/all problems solved) of AoC in Rust, and my personal experience shows that while recursive solution might be fine for example data, it typically does not scale/work for real input or part 2 of problems. it's imho always better to do iteration approach...
Lots of algorithms are "naturally" recursive, though: anything where converting it into an iteration requires that you maintain some form of stack yourself that has similar entries to the program stack in the recursive version. I tend to find that these are easier to write, read, and debug when written in their recursive forms, and will generally use the same big-O amount of memory in either form (though the iterative version may have a smaller constant).
If the maximum recursion depth is input-dependent/unbounded then the recursive version may well blow up the stack and fail when the iterative version would have succeeded (by heap-allocating its "stack" state) and therefore you might need to do something about that, though sometimes "making the stack way bigger" might be a simpler solution than rewriting it as an iteration.
But, when the recursion depth is bounded (as it seems to be here) then going out of your way to write an iterative version may not be an improvement. I've not tried solving this specific problem though, so take this as a very general statement
Of course there are many other algorithms that are more efficient as iterations, but in my experience giving software engineering interviews I've found that many people take "use iteration instead of recursion" far too strongly and tie themselves in knots trying to write an algorithm iteratively when it would have been perfectly reasonable to write the recursive form, or at least write the recursive form first to get the details of the algorithm down and then convert it into an iteration in a mostly-mechanical way.
