Scribd
Upload
13 views3 pages

What Is A Recursive Algorithm?

A recursive algorithm solves problems by calling itself with smaller input values, utilizing a base case to terminate the recursion and a recursive step to compute results. There are four types of recursion: direct, indirect, and tail recursion, each defined by how the function calls itself. Understanding these types helps in effectively implementing recursive solutions to problems.

Uploaded by

Azharr Nawaz
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
13 views3 pages

What Is A Recursive Algorithm?

A recursive algorithm solves problems by calling itself with smaller input values, utilizing a base case to terminate the recursion and a recursive step to compute results. There are four types of recursion: direct, indirect, and tail recursion, each defined by how the function calls itself. Understanding these types helps in effectively implementing recursive solutions to problems.

Uploaded by

Azharr Nawaz
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

What Is a Recursive Algorithm?

A recursive algorithm calls itself with smaller input values and returns the
result for the current input by carrying out basic operations on the returned
value for the smaller input. Generally, if a problem can be solved by applying
solutions to smaller versions of the same problem, and the smaller versions
shrink to readily solvable instances, then the problem can be solved using a
recursive algorithm.

 Base Case: It is nothing more than the simplest instance of a problem,


consisting of a condition that terminates the recursive function. This base
case evaluates the result when a given condition is met.

 Recursive Step: It computes the result by making recursive calls to the


same function, but with the inputs decreased in size or complexity.

Different Types of Recursion

There are four different types of recursive algorithms, you will look at them
one by one.
 Direct Recursion

A function is called direct recursive if it calls itself in its function body


repeatedly. To better understand this definition, look at the structure of a
direct recursive program.

int fun(int z){

fun(z-1); //Recursive call

In this program, you have a method named fun that calls itself again in its function
body. Thus, you can say that it is direct recursive.

 Indirect Recursion

The recursion in which the function calls itself via another function is called
indirect recursion. Now, look at the indirect recursive program structure.

int fun1(int z){ int fun2(int y){

fun2(z-1); fun1(y-2)

} }
In this example, you can see that the function fun1 explicitly calls fun2, which is
invoking fun1 again. Hence, you can say that this is an example of indirect
recursion.

 Tailed Recursion

A recursive function is said to be tail-recursive if the recursive call is the last


execution done by the function. Let’s try to understand this definition with
the help of an example.

You might also like