Skip to content

16. Recursion

Jump to bottom
Madhav Anand edited this page Dec 2, 2020 · 3 revisions

Notes Link

  1. 16.1 Recursion: Stack Frames & Warm Up ✅
  2. 16.2 Recursion: Stack Frames & Sprint ✅
  3. 16.3 Recursion: String & Race
  4. 16.4 Recursion: Advanced

Introduction

This is a: 🔫 Topic & Challenging
Technical Definition: When a function calls itself to make the problem smaller is called recursion.

Concise Code Tips

  1. Run for 0 !0
  2. Empty Return to void return ;
  3. if else in function = if return return

Warm up Questions (5)

  1. Find the sum of n natural numbers

Sum(n) = n + Sum(n-1) [n + n-1 + ...]

  1. Find the sum of n natural numbers

Sum(n) = i + (n,i+1) [1 + 2 + ...]

  1. Find n exponent p using recursion, where p is a whole number.

n p = n x n p-1

  1. Find the factorial of number n using recursion.

n! = n x (n-1)!

  1. Print the nth Fibonacci number where default values F(0)=0, F(1)=1

F(n) = F(n-1) + F(n-2)

Sprint Questions (5)

  1. Check if the array is sorted strictly increasing.

arr[0]<arr[1] && (arr+1, n-1)

  1. Print the n natural numbers in decreasing order.

Pass-Print-Repeat(dec)

  1. Print the n natural numbers in increasing order.

Wait-Print-Repeat(inc)

  1. Find the first occurrence of a number in an array.

Return if got else Repeat

  1. Find the last occurrence of a number in an array.

Reach to Base, if got keep returning otherwise find.

Race Questions (8)

  1. Reverse a given string

substr() and length function

  1. Replace a pi with 3.14 in string.

if ... else ...

  1. Tower of Hanoi

Three towers A(Source), B(Helper), C(Destination) we can only move one block at a time and order can't be bigger > smaller
Number of disks to moved from source to destination via auxilary
Recources Video Animation

  1. Remove all duplicates from a string.

asdf

  1. Move x to the end.

asdf

  1. Generate all substrings of a string.

Recursively add and don't add

  1. Generate substrings with ASCII number.

Recursively add three

  1. All possible words from digits in keypad.

asdf

Challenge Questions (8)

  1. Print all the possible permutation of a string

asdf

  1. Count the number of paths possible from a start point to end point in gameboard.

asdf

  1. Count the number of path possible in a maze.

Print Version Left

  1. Tiling Problem : Given a "2xn" board and tiles of size "2x1", count the number of ways to tile the given board using these tiles.

Find the number of ways to tile the floor with "2x1" tiles (1x2 and 1x1 tiles)
Notation is always Rows x Columns like in matrices.
Rows are fixed to "2"

Some Observations

  1. When a function calls a function, the first function is paused.

Clone this wiki locally