Structural Recursion is one of the concepts of recursive function. The main thing about structural recursion is we can make a clear mental model of what is happening. Substitution method can be used to explain the concept of structural recursion. In each recuraion a new block is created which is similar to the previous recursion block, only difference being the size of parameter decreases. The recursion stops and starts returning when the parameter size become 0. The structural recursion can be clearly explained using an example.
- def sum(a):
- if null(a):
- return 0
- return first(a) + sum(reat(a))
In the above example, null(a) returns true if length of a is 0, first(a) returns the first element of list a and rest(a) returns the list without first(a). When we call the function sum(a), a block is created and if null(a) is true, returns 0, Else it will store the first element and location in a stack and create a new block for sum(rest(a)). Now the same process continue, until null(a) becomes true.
Another important feature of structural recursion is, it will calcuate the result only when the creation of new blocks terminate and each function starts returning it value.
The process may be faster with respect to time, but with respect to space, it use a large amount of space in the stack to store the intermediatory blocks.