About recursion depth

General
1

I tried to print the max recursion depth:

fn recursion(n: Int):
	print(n)
	recursion(n + 1)

fn main():
	recursion(0)

Such code would end at 1000 loops in Python, but It never ends in Mojo.

I’ve seen that Mojo has some magical built-in optimazations, I thought the code might have been optimized. To prevent any optimization, I introduced random values:

from random import random_si64

fn recursion(n: Int):
	print(n)

	var rand = Int(random_si64(1, 10))
	
	recursion(n + rand)

fn main():
	recursion(0)

But nothing changes.

So my question is:

  1. There isn’t a max recursion depth limitation, is this correct? Or am I testing in a wrong way?
  2. Why the runtime memory cost doesn’t change? It’s expected to increase due to more and more call stacks?

Updated
The program crashes if there are two recursion(n+1), not sure why:

fn recursion(n: Int):
	print(n)
	recursion(n + 1)
	recursion(n + 1)

fn main():
	recursion(0)
2

It’s tail call optimization. See this post for a nice breakdown: What is Mojo's approach to tail call optimization? · modular/modular · Discussion #519 · GitHub

In the case where you have two recursive functions tail calll optimization can’t happen on the first call since TCO requires that the fn call be the last op in a function.

2 Likes
3

Actually it still could happen do to inlining.

4

I’m curious to know how would in lining fix this. I’d assume that since the function has two calls to itself, each time you inline one of those calls, wed actually be increasing the number of times the function calls itself.

5

If you inline one of the function calls, you then have normal tail recursion.

6

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.