Recursive Algorithms

How Recursion Works in Memory ?

  1. Stack
  2. Static data area
  3. Code area
  4. Heap
  1. Incoming parameters
  2. Return value
  3. Temporary storage
  4. Saved state information
  5. Outgoing parameters

Memory Allocation in Recursion

What is recursion used for?

Base cases and Recursion

Basic Recursion

sum(5)5 + sum(4)5 + (4 + sum(3))5 + (4 + (3 + sum(2)))5 + (4 + (3 + (2 + sum(1))))12 + 1; // unwinding start3 + 3;4 + 6;5 + 10;15

Tail Recursion

sum(5)5 + sum(4)5 + (4 + sum(3))5 + (4 + (3 + sum(2)))5 + (4 + (3 + (2 + sum(1))))5 + (4 + (3 + (2 + 1)))15
  • If exponent is 0, then power is 1. This is the base condition of our recursive function.
  • If exponent is negative, then power is 1 / (x ^ -y). Which uses recursive call to _pow_recursionfunction for computing the value of (x ^ -1) i.e. 1 / _pow_recursion(base, -expo).
  • If exponent is positive, then calculate power normally using x ^ y. Computing x ^ y also makes a recursive call i.e. base * _pow_recursion(base, expo - 1)

Using Basic Recursion

Using Divide and Conquer.

--

--

--

Developer | Software engineer in process | Facebook | instagram | Student in Holberton school

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

TESTNET IS LIVE!

TIME IS RUNNING OUT. PROTECT YOUR VMWARE INVESTMENTS

Is Haskell fast?

Introducing the Cloud Native Compute Foundation (CNCF)

CNCF Projects

Essential Data Structures and Algorithms for Coding Interviews

TOP 10 PROGRAMMING LANGUAGES USED IN AI CHATBOT BUILDING

TOP 10 PROGRAMMING LANGUAGES USED IN AI CHATBOT BUILDING

Protected view-only Postgres schemas

All About Namespaces

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Cristian Mendoza

Cristian Mendoza

Developer | Software engineer in process | Facebook | instagram | Student in Holberton school

More from Medium

Algorithms: Recursion/BackTracking, Permutations

Remove Covered Intervals🚲

HUFFMAN CODING

Arrays for the uninitiated