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)
for(int i=1 to n)
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
We shall get into more depth about recursion in upcoming articles.
More from this Category
Learn about typographical hierarchy and font selection.
A great deal of audience is attracted if it looks hot. This pretty much what “UI” is all about. Now the audience is going to stay if it has a lot to offer. This is “UX”
What do colors mean?
Learn about color, color combination and the tools you will need to create your own color palette.
Design is less about how they are happening, it’s more about how dope it looks while they are happening.
An introduction to an elaborate series on Design Concepts.