Day1: Iteration, Recursion, Memoization

Learnings Day1: In Programming World how do you implement something with Iteration, Recursion, Memoization

Let's see 1st Concept of Iteration: What do you understand by Iteration

Iteration is a core concept in programming and is essential for traversing data structures, performing repetitive operations, and solving problems efficiently

How can we achieve iteration? That's where the looping constructs come into the picture, such as for loops, while loops, or do-while loops, depending on the programming language or environment you're working with

Eg: Using an iterative approach and displaying the result for the factorial of a number

As I am a Golang developer, I started to implement in Go for Day1 the concepts.

package main

import (
    "fmt"
)
// 5 = 1 * 2 * 3 * 4 * 5 = 120
//Iteration approach
func factorial(num int) int {
     value := 1
     for i:=1 ; i<=num ; i++ {
           value = value * i
   }
 return value
}
func main() { 
    num := 5
    res := factorial(num)
    fmt.Println(res)
}

package main

import (
    "fmt"
)

// 5 = 5 * 4 * 3 * 2 * 1
//Iterative approach
func factorial(num int) int {
     value := 1
     for i:=5 ; i>=num ; i-- {
           value = value * i       
   }
return value
}

func main() {
    num := 1
    res := factorial(num)
    fmt.Println(res)
}

Now Let's see the Concept of Recursion: What do you understand by Recursion?

Recursion: In addition to basic iteration, there are more specialized iteration techniques like recursion, where a function calls itself to solve a problem by breaking it down into smaller subproblems. Recursion is often used in algorithms that require dividing a problem into smaller instances until a base case is reached.

//5 = 5 * 4!
//4 = 4 * 3!

package main
import (
    "fmt"
)
func fact(num int) int {
    if num == 1 {
      return 1
}
   return num * fact(num-1)
}
func main() {
    num := 5 
res := fact(num)
fmt.Println(res)
}

Now Let's see the Concept of Memoization: What do you understand by Memoization?

Memoization: Think of it as keeping a diary of your experiences. Each time you solve a calculation, you jot down the result and store it in your diary. When faced with a similar calculation later on, you simply flip through the pages of your diary, find the previously calculated result, and use it without going through the entire process again.

In the World of programming, memoization works similarly. It helps optimize algorithms and computations by storing previously calculated results. This way, when a similar computation is encountered again, the stored result can be retrieved instantly, avoiding the need for redundant calculations.

1. We declare a global variable cache which is a map that will store the factorial values.

2. The fact function now checks if the factorial value for a particular number is already present in the cache. If it is, we directly retrieve it from the cache and return the value, avoiding redundant calculations.

3. If the factorial value is not present in the cache, we compute it as before: result := num * fact(num-1). However, we also store this computed value in the cache for future use.

4. In the main function, we call fact with the desired number (num in this case) and print the result.

package main

import (
    "fmt"
)
var cache = make(map[int]int)
func fact(num int) int {
    if num == 1 {
        return 1
    }
    if val, ok := cache[num]; ok {
        return val
    }
    result := num * fact(num-1)
    cache[num] = result
    return result
}

func main() {
    num := 5
    res := fact(num)
    fmt.Println(res)
}

Fibanocci : Iteration

package main 

import ( 
"fmt"
)
// Iteration
func fib(pos int) int {
         a: = 0 
         b:=1
         c :=0 
         for i:=2; i<pos ; i++{
              c = a+b
              a = b 
              b = c
         }
         return c;
}
func main(){
   position := 9
   result := fib(position)
   fmt.Println(result) 
}

Recursion Fibanocci:

//** now with recursion
//fib(9) = fib(7)+fib(8)
//fib(7) = fib(6)+fib(5)

package main 

import ( 
"fmt"
)

func fib(pos int) int {
    if (pos == 0) {
     return 0;
     }   
     if(pos==1 || pos == 2){
     return 1;
     }   
     return fib(pos-1)+fib(pos-2)
}


func main(){
   position := 9
   result := fib(position)
   fmt.Println(result) 
}

Memoization :

// when we want to get fib(9) -- 5 times we calc fib(5) -- but we don't want
// save the value in cache like map in go - we call it a dictionary in python // in java we implement map using hashmap


package main

import (
    "fmt"
)

var cache = make(map[int]int)

func fib(pos int) int {
    if pos == 0 {
        return 0
    }

    if pos == 1 || pos == 2 {
        return 1
    }

    if val, ok := cache[pos]; ok {
        return val
    }

    result := fib(pos-1) + fib(pos-2)
    cache[pos] = result
    return result
}

func main() {
    position := 9
    result := fib(position)
    fmt.Println(result)
}

Github Link : https://github.com/tknoptn/10Day10C/tree/main/Day1-Assignment

Completed Day 1 of the coding challenge, pushing boundaries and embracing growth on the path to becoming a skilled programmer.