Recursion: Introduction

by | Jun 18, 2017

Recursion is a process in which a function calls itself. It can be used at places where the value of a function at a given input can be evaluated using the value of the function at other inputs.

Consider the following pseudocode:

int function(int n)


int s=0;

for(int i=1 to n)


return s;


The code evaluates the sum of the first n natural numbers. The recursive implementation of the same could be thought as follows:


Sum of first ‘n’ natural numbers = Sum of first (n-1) natural numbers+n 


However, there is a catch. Sum of n natural numbers only makes sense for non-negative values of n. As the sum of (-1) natural numbers is not defined, our formula is valid only for n>0. So, we must stop using the formula at the moment function(0) is called. This condition/constraint which marks the end of the recursive behavior is called the base case of the recursive function.


The pseudocode for the given logic is as follows:

int function(int n) //n>0


if(n==0) return 0; //base case ,returns 0 as sum of ‘0’ natural numbers=0

return (function(n-1)+n);  //returns the value for given n using recursive formula



Here is another interesting example of the Fibonacci sequence. If F(n) represents the value of the n-th Fibonacci number, we have:


which represents a recursive formula.



As the term F(n) is valid for n>=1, the given formula holds true for n>=3. Thus, we can evaluate F(n) using the formula if n>=3 and return the values directly for n=1,2(Base case).


The pseudocode using this logic is as follows:

int find(int n)


if(n==1)return 1; //F(1)=1 base case #1

if(n==2)return 1; //F(2)=1 base case #2

return (find(n-1)+find(n-2));


We shall get into more depth about recursion in upcoming articles.





Submit a Comment

Your email address will not be published. Required fields are marked *

More from this Category