Recursion in functions is a technique where a function calls itself directly or indirectly to solve a problem. It's a powerful tool, particularly suited for problems that can be broken down into simpler, similar sub-problems. To implement recursion, a function should have two main components: a base case, which stops the recursion, and the recursive step, where the function calls itself with a modified parameter.

An example is a factorial function, where the factorial of a number n (denoted as n!) is n * (n-1)!. The base case here is when n is 0 or 1 (since 0! and 1! are 1), and the recursive step involves calling the factorial function with n-1.

The advantages of recursion include simplicity and clarity, especially for problems naturally fitting the recursive paradigm, like tree traversals or sorting algorithms like QuickSort. Recursive solutions are often more straightforward and easier to understand than their iterative counterparts.

However, recursion also has disadvantages. It can be less efficient due to the overhead of multiple function calls and stack usage, potentially leading to stack overflow in deep recursion scenarios. Furthermore, not all problems are amenable to recursion, and sometimes iterative solutions are more efficient and straightforward. Hence, the use of recursion should be carefully considered, keeping in mind the problem's nature and the language's efficiency in handling recursive calls.

The decision to use a function over a procedure in structured programming hinges on the requirement of a return value. Functions are appropriate when a specific task needs to be performed and a result must be returned to the part of the program where the function was called. This is particularly relevant in scenarios involving calculations, data processing, or any situation where the outcome of the task is needed for further operations. For example, a function to calculate the area of a shape, find the maximum value in a list, or convert temperatures between units is more suitable because these tasks inherently produce a result that is usually required for subsequent computations or decisions.

Procedures, on the other hand, are better suited for tasks that perform actions rather than calculations, such as displaying information, modifying global state, or executing a series of steps that don't necessarily produce a return value. In essence, if the task at hand involves producing and delivering a specific piece of data or outcome, a function is the right choice; if it's more about performing an action or a series of actions, a procedure is more appropriate.

'Passing by value' and 'passing by reference' are two methods of providing input to functions, and they significantly differ in how they handle the arguments.

When parameters are passed by value, the function receives a copy of the actual data. This method is primarily used when the function needs to work with the provided data without altering the original values. In this scenario, any modifications made to the parameters within the function do not reflect back in the original arguments. For instance, if a function is passed a number by value and it modifies that number, the change is not seen outside the function. This approach is safer as it guards against unintended side-effects.

Conversely, passing by reference involves passing the actual reference (or address) of the data to the function. This means any changes made to the parameters inside the function are directly reflected in the original arguments. It is useful when the function needs to modify the input data or when passing large data structures where copying would be inefficient. However, it increases the risk of unintended modifications to the data, which can lead to bugs and errors in the program. Choosing between these two methods depends on the specific requirements of the function and the desired outcome in the program.

Anonymous functions, also known as lambda functions, are functions that are defined without a name. They are typically short and designed to be used where a function is required for a short period, often passed as an argument to other functions or used in place of a small, one-off function.

An example of anonymous function usage is in sorting operations where you might want to sort objects based on a particular attribute using a short function passed directly into the sorting method. In programming languages that support first-class functions, such as JavaScript or Python, anonymous functions are quite prevalent and useful in functional programming paradigms.

In the context of structured programming, especially in languages that don’t primarily support anonymous functions, their relevance diminishes. Structured programming generally emphasizes clarity and the use of named functions and procedures with a clear structure. However, in more advanced contexts or in languages that bridge structured and functional programming paradigms, anonymous functions can still be useful for creating concise and readable code, especially for short, single-purpose operations. They should be used judiciously, keeping in mind the readability and maintainability of the code.

The concept of 'scope' in functions is pivotal in determining the accessibility and lifetime of variables within a program. Scope can be primarily classified into two categories: local and global. Local scope refers to variables defined within a function. These variables are only accessible and modifiable within the function itself, thereby preventing any unintended interference from other parts of the program. This encapsulation ensures that the function's internal workings remain independent and isolated, contributing to the overall modularity and error reduction in the program. For instance, a variable declared within a function to store a temporary calculation result cannot be accessed outside that function.

On the other hand, global scope pertains to variables declared outside any function, usually at the top level of the program. These variables are accessible from any part of the program, including within functions. However, their use is generally discouraged in structured programming due to potential issues with maintainability and the risk of unintended modifications from different parts of the program. Excessive reliance on global variables can lead to 'global state' issues, where debugging and tracking the flow of data become challenging. Effective use of scope in functions thus plays a crucial role in maintaining a clean, understandable, and maintainable codebase.