Structural Recursion

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
  • else:
  • 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.

Advertisements

About Odol Shinu

I've completed my B Tech in Information Technology in 2010 from Government Engineering College Sreekrishnapuram Palakkad under Calicut University.

Posted on September 14, 2010, in Python. Bookmark the permalink. 1 Comment.

  1. Well, please read:

    http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Structural_versus_generative_recursion

    It seems you have got a few ideas mixed up: tail, structural, generative etc …

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: