# Recursion: Introduction

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.

# More from this Category

## Typography

Learn about typographical hierarchy and font selection.

## UX/UI : Before We Prototype.

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”

## A Colorful Impact

What do colors mean?

## Color: The Basics

Learn about color, color combination and the tools you will need to create your own color palette.

## Design Insight : One More Definition

Design is less about how they are happening, it’s more about how dope it looks while they are happening.

## Is Design Important?

An introduction to an elaborate series on Design Concepts.

## 0 Comments