Recursion

Welcome to blog about Computer Science!

My name is Kamilya Altynbekova and I am a first year student at Nazarbayev University. Since the childhood I was interested in computers and at high school began attending programming classes. Simple interest has grown up to passion and this passion brought me to Computer Science (CS) department of my university.

As a student I often face a problem of finding resources that provide short and simple explanation of needed material. Some concepts are either explained in a very complex way or too simply for true understanding. Here I will try to explain some concepts that are very useful not only for CS majors, but for all science students. 

General definition

This blog is going to be about recursion. I have chosen this concept from my "Fundamentals of Programming" syllabus, but it is widely used in other sciences besides CS.

First of all, let’s take a look at the image on the right. Notice, that each inner image is just a repetition of the initial image.  This picture is a simple example of the recursion. According to Cambridge University Press Dictionary term recursive is “involving doing or saying the same thing several times in order to produce a particular result or effect”

There are many other examples. Physicist can probably think about two mirrors placed towards each other. The recursion occurs as the mirrors infinitely reflect each other. Example from Math is the Fibonacci sequence. We constantly repeat summing up the last two numbers in the sequence to obtain the next one.  

Often recursion is difficult to understand because it has a specific meaning in a variety of areas and disciplines. However, the main idea of repetition always remains the same.

Recursion in Computer Science

Most commonly recursion is used in computer science and programming where it has very specific definition. Recursion in programming is “a technique involving the use of a procedure or function that can call itself”. 

The classical example of problem requiring such technique is a factorial function. Factorial of some number x is simply the product of all integers from 1 to this number x. Factorial of number 10 is 10!=1*2*3*4*5*6*7*8*9*10, where “!” is the notation used for factorial. Notice that it is possible to rewrite it in the form 10! = 10*9! It is true for any factorial, so generally x! = x*(x-1)!

Now it is possible to see how this problem relates to our topic.  In order to find a factorial of 5, it should be multiplied by factorial of 4 which is 4 multiplied by factorial 3 and so on. We use factorial to find factorial, so the recursion is useful here. 

Now when we can see the pattern algorithm for a program can be developed. Recursive function usually consists of two main elements: base step and recursive step. Base step sets condition for function to stop calling itself. It prevents program from running infinitely and crashing. In our example with factorial such condition is reaching the number 1. In recursive case function is allowed to call itself. While x more than 1 the formula obtained above is simply used. (click here for more details)

Despite the existence of the alternative solutions recursion makes the solution much simpler and cleaner.

We considered the general algorithm without any actual code because our goal is just to understand the general concept. I hope that we achieved this goal and you have an idea of what is recursion.

Visit my blog for new blogs and feel free to comment!

References:

Explanation of Recursion. (n.d.). Retrieved September 23, 2014, from http://www.programmerinterview.com/index.php/recursion/explanation-of-recursion/