[go: up one dir, main page]
Scribd
Upload
39 views9 pages

Recursion Basics for CS Students

Recursion is a process where a function calls itself directly or indirectly to solve a problem. For a recursive function to terminate, it must have a base case condition that stops the recursion. With each recursive call, the function state changes and moves toward the base case. Recursion differs from iteration in that recursion requires extra memory for each call, which could lead to stack overflow for infinite recursion, while iteration uses the same memory space. Common types of recursion include linear, tail, binary, and mutual recursion.

Uploaded by

mark brian Bautista
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
39 views9 pages

Recursion Basics for CS Students

Recursion is a process where a function calls itself directly or indirectly to solve a problem. For a recursive function to terminate, it must have a base case condition that stops the recursion. With each recursive call, the function state changes and moves toward the base case. Recursion differs from iteration in that recursion requires extra memory for each call, which could lead to stack overflow for infinite recursion, while iteration uses the same memory space. Common types of recursion include linear, tail, binary, and mutual recursion.

Uploaded by

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

Data Structures and

Algorithms
Prepared By
Engr. Regine Jesa J. Palara, MIT
Fundamentals of Recursion

❖ Recursion – is a process where a function calls itself one


or multiple times to solve a problem.
❖ Any function that calls it self is recursive.
❖ Recursion that involves a method directly calling itself is
called direct recursion.
❖ Indirect recursion occurs when a method invokes another
method, eventually resulting in the original method being
invoked again.
❖ When a recursive function fails to stop recursion, infinite
recursion occurs.
Fundamentals of Recursion

❖ A recursive algorithm must:


❖ Have a base case – A base case is the condition that
allows the algorithm to stop recurring.
❖ Change its state and move toward the base case – A
change of state means that some data that the
algorithm is using is modified.
❖ Call itself, recursively.
Recursion vs. Iteration

❖ Iteration is a process of repeating a set of instructions.


This is also known as “looping”.
RECURSION ITERATION
It terminates when a base case It terminates when a condition is
is reached. proven to be false.
Each recursive call requires Each iteration does not require
extra memory space. extra memory space.
An infinite recursion may cause An infinite loop could loop forever
the program to run out of since there is no extra memory being
memory and may result in created.
stack overflow.
An infinite loop could loop Iterative solutions to a problem may
forever since there is no extra not always be as obvious as a
memory being created. recursive solution.
Types of Recursion

❖ Linear recursion – The function calls itself once each


time it is invoked. Ex. finding the factorial
Types of Recursion

❖ Tail recursion – The function makes a recursive call as its


very last operation. Ex. finding the greatest common
divisor of two (2) non-zero integers
Types of Recursion

❖ Binary recursion – The function calls itself twice in the


run of the function. Ex. Fibonacci series
Types of Recursion

❖ Mutual recursion – The function works in a pair or a


group. Ex. determining whether an integer is even or odd
THE END

You might also like