Tag Archives: functions

Recursion – The basics

Recursion – The basics


COMPUT: a programming technique where a routine performs its task by delegating part of it to another instance of itself.

For new computer science students, the concept of recursive programming is often difficult. Recursive thinking is difficult because it almost seems like circular reasoning. It’s also not an intuitive process; when we give instructions to other people, we rarely direct them recursively.

For those of you who are new to computer programming, here’s a simple definition of recursion: Recursion occurs when a function calls itself directly or indirectly.

A classic example of recursion
The classic example of recursive programming involves computing factorials. In mathematics, the factorial of a nonnegative integer, n (denoted n!) is the product of all positive integers less than or equal to n. For example, 5! is the same as 5*4*3*2*1, and 3! is 3*2*1.

An interesting property of a factorial is that the factorial of a number is equal to the starting number multiplied by the factorial of the number immediately below it. For example, 5! is the same as 5 * 4! You could almost write the factorial function as:

int factorial(int n)
   return n * factorial(n - 1);

Listing 1. First cut factorial function

However, there is a small problem with this; it will run forever because there is no place where it stops calling itself. It therefore needs a condition to tell it to stop. Since a factorial is for positive numbers only it makes sense to stop the recursion when the input is 1 and return 1 as the result. The modified code will look like this:

int factorial(int n)
   if(n == 1)
      return 1;
      return n * factorial(n - 1);

Listing 2. better factorial function

As you can see, as long as the initial value is above zero, this function will terminate. Note that more work will need to be done to guard again invalid initial values.

The point at with the recursion is stopped is called the base case. A base case is the bottom point of a recursive program where the operation is so trivial as to be able to return an answer directly. In the case of a factorial 1! = 1. All recursive programs must have at least one base case and must guarantee that they will hit one eventually; otherwise the program would run forever or until the program ran out of memory or stack space.


Basic steps of recursive programs
All recursive programs follows the same basic sequence of steps:
1: Initialize the algorithm. Recursive programs often need a seed value to start with.
2: Check to see whether the current value(s) being processed match the base case. If so, process and return the value.
3: Redefine the answer in terms of a smaller or simpler sub-problem or sub-problems.
4: Run the algorithm on the sub-problem.
5: Combine the results in the formulation of the answer.
6: Return the results.


Advantages and drawbacks of recursion

Main advantage of recursion is programming simplicity. When using recursion, programmer can forget for a while of the whole problem and concentrate on the solution of a current case. Then, returning back to the whole problem, base cases (it’s possible to have more than one base case) and entry point for recursion are developed.

On the other hand, recursion has a serious disadvantage of using large amount of memory. Moreover, for most programming languages, recursion use stack to store states of all currently active recursive calls. The size of a stack may be quite large, but limited. Therefore too deep recursion can result in Stack Overflow. To resolve this problem recursion can be simulated, using loop and stack data structure.

Method Vs Function

Method Vs Function

A function is a piece of code that is called by name. It can be passed data to operate on (ie. the parameters) and can optionally return data (the return value).

All data that is passed to a function is explicitly passed.

A method is a piece of code that is called by name that is associated with an object. In most respects it is identical to a function except for two key differences.

1. It is implicitly passed the object for which it was called

2. It is able to operate on data that is contained within the class (remembering that an object is an instance of a class – the class is the definition, the object is an instance of that data)
(this is a simplified explanation, ignoring issues of scope etc.)


A method is on an object.A function is independent of an object.

For Java, there are only methods.For C, there are only functions.

For C++ it would depend on whether or not you’re in a class.