[go: up one dir, main page]
Scribd
Upload
7 views3 pages

Recursion

Recursion involves functions that call themselves with new parameters, requiring a base case to terminate the recursion. Recursive algorithms can be shorter but may have higher space complexity due to multiple instances of variables being stored in the stack. An example function demonstrates how recursion works by progressively reducing the parameters until the base case is reached.

Uploaded by

doejohnny549
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
7 views3 pages

Recursion

Recursion involves functions that call themselves with new parameters, requiring a base case to terminate the recursion. Recursive algorithms can be shorter but may have higher space complexity due to multiple instances of variables being stored in the stack. An example function demonstrates how recursion works by progressively reducing the parameters until the base case is reached.

Uploaded by

doejohnny549
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

Recursion

Functions which call themselves

They have to be a function

Functions usually accept one or more PARAMETERS to work with

Recursive functions

A recursive function is one which makes a new call to itself partway through, passing a new value as
a parameter

It is a form of iteration

When the function recurses it begins again with a new parameter or set of parameters

The current state of the registers and variables are added to the stack

This continues until a Base case is met one which can be determined immediately and doesn’t
require another function call to get a result

2 golden rules for recursive algorithms

All recursive functions must have a base case or exit clause or which causes the recursion to end and
return a value; this is usually the state where a result can be returned without having to do
something else first

If the base case is never reached you get an overflow error

Every recursive call makes progress towards the base case

Recursive solutions are often shorter but have a larger space complexity each recursive call adds a
new set of data (frame) to the stack and creates multiple instances of each variable

You demonstrate recursive algorithms by tracing is by drawing a diagram

Function calculate(num1, num2)

If num1 == num2 then

Return num1

Elseif num1 <num2 then

Return calculate(num1, (num2-num1)


Else

Return calculate (num2, (num1 – num2))

Endif

Endfunction

Num1

def calculate(num1, num2):

while num1 != num2:

if num1 < num2:

num2 = num2 – num1

else

temp = num1 – num2

num1=num2

num2 = temp

calculate(5) is called.

calculate(5) -> 5 + calculate(4)

calculate(4) -> 4 + calculate(3)

calculate(3) -> 3 + calculate(2)

calculate(2) -> 2 + calculate(1)

calculate(1) returns 1

calculate(2) returns 2 + 1 = 3

calculate(3) returns 3 + 3 = 6

calculate(4) returns 4 + 6 = 10
calculate(5) returns 5 + 10 = 15

You might also like