Recursion is so fundamental because...

#recursion

#java

#python

#c++

#interviewing

#subproblems

Recursion is so fundamental because it overlaps with literally every other category of problem that we could get asked:

Linked lists? Print a linked list in reverse order.
Strings? Determine if a string is a palindrome.
Trees and graphs? Have fun doing an iterative DFS.
Dynamic programming? Okay do you get my point? This is all recursive.
If we were to draw out our categories as a Venn diagram, it would look something like this:

Recursion venn diagram