Two fixed-size algorithms were used to investigate natural river networks: the box-counting method and the sandbox method. The first produces good results for nonnegative moment orders, q, but suffers from border effects. The second solves border problems and is particularly adapted to negative moment orders for the reconstruction of the right side of the multifractal spectrum, f(α). In the box-counting applications the influence of the mesh number was investigated in the range 20 to 100, for moment orders from 0 to 10, showing that the error in the assessment of the generalized fractal dimensions is not greater than 3%. The sandbox method was applied to the river networks for the first time, and the theoretical expression of the information entropy was derived. Results were obtained also for negative moment orders, showing that the analyzed river networks are multifractal and non-plane-filling structures. The sandbox method avoids border effects, as verified through an application to a square portion extracted from a river network. Result analysis suggests a dependence of the f(α) spectra from the lithologic characteristics of the source rocks.