So i have a recursive search algorithm here,
Search(graph G = (V, E), vertex s ∈ V, integer k)
1 mark vertex s as number k
2 set k ← k + 1
3 let L be the linked list of neighbors for s
4 repeat until all entries in L are marked with an X
5 mark the first un-marked entry y in L with an X (going from left to right in the list)
6 let v be the vertex named in entry y
7 if v is not yet marked with a number then set k ← Search(G, v, k)
8 return k
Here's the adjacency list box diagram,
It seems to me that it is a Breadth-First-Search since it visits the nodes at level k before the nodes of level k+1. Depth-First-Search would explore as far as possible along each branch before backtracking. Is it?
No, this is depth first search. You recursively explore children before siblings.
btw, if someones claims they have a recursive algorithm for breadth-first-search, you should look at it carefully. Either it is wrong, or a convoluted simulation of no use.