//start adsense code //end adsense code

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)

s=s+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:

F(n)=F(n-1)+F(n-2)

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.

 

 

 

0 Comments

Submit a Comment

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

More from this Category