Recursion in Verilog

Verilog supports recursive modules, although they are not commonly used due to the hardware-oriented nature of the language. Here’s an example demonstrating recursion in Verilog:

module factorial(
    input wire [3:0] n,
    output reg [31:0] result
);

    always @(*) begin
        if (n == 0)
            result = 1;
        else if (n == 1)
            result = 1;
        else begin
            factorial smaller_fact(.n(n - 1), .result(result));
            result = n * result;
        end
    end

endmodule

module fibonacci(
    input wire [3:0] n,
    output reg [31:0] result
);

    always @(*) begin
        if (n < 2)
            result = n;
        else begin
            reg [31:0] fib1, fib2;
            fibonacci fib_n_minus_1(.n(n - 1), .result(fib1));
            fibonacci fib_n_minus_2(.n(n - 2), .result(fib2));
            result = fib1 + fib2;
        end
    end

endmodule

module testbench;
    reg [3:0] n;
    wire [31:0] fact_result, fib_result;

    factorial fact(.n(n), .result(fact_result));
    fibonacci fib(.n(n), .result(fib_result));

    initial begin
        n = 7;
        #10 $display("Factorial of %d is %d", n, fact_result);
        #10 $display("Fibonacci of %d is %d", n, fib_result);
        $finish;
    end

endmodule

This Verilog code demonstrates recursion using two classic examples: factorial and Fibonacci sequence.

The factorial module calculates the factorial of the input n. It uses recursion by instantiating itself for n-1 when n is greater than 1.

The fibonacci module calculates the nth Fibonacci number. It uses recursion by instantiating itself twice for n-1 and n-2 when n is 2 or greater.

In the testbench, we instantiate both modules and calculate the factorial and Fibonacci number for n = 7.

Note that while this code demonstrates the concept of recursion in Verilog, it’s important to understand that Verilog is a hardware description language. In real hardware designs, recursive structures are typically unrolled or implemented iteratively for efficiency and practicality.

To run this Verilog code, you would need to use a Verilog simulator such as Icarus Verilog or ModelSim. The output would look something like this:

Factorial of 7 is 5040
Fibonacci of 7 is 13

Remember that in hardware design, recursive algorithms are often replaced with iterative solutions or lookup tables for better performance and resource utilization.