CODE & ALGO

Recursion

Recursion

Infinite Recursion

package main

import "fmt"

func recursion1(n int) {
	if n >= 5 {
		return
	}
	fmt.Printf("n=%d\n", n)
	recursion1(n)
}

func main() {
	n := 0
	recursion1(n)
}

*********************
Output
*********************
n=0
n=0
n=0
^Csignal: interrupt (infinite printing ...)

Recursion with base case

package main

import "fmt"

func recursion2(n int) {
	if n >= 5 {
		return
	}
	fmt.Printf("n=%d\n", n)
	recursion2(n + 1)
}

func main() {
	n := 0
	recursion2(n)
}

*********************
Output
*********************
n=0
n=1
n=2
n=3
n=4
package main

import "fmt"

func recursion3(i, counter int) {
	if i > counter {
		return
	}
	fmt.Println("Roger")
	recursion3(i+1, counter)
}

func main() {
	i := 1
	counter := 5
	recursion3(i, counter)
}


*********************
Output
*********************
Roger
Roger
Roger
Roger
Roger
package main

import "fmt"

func recursion4(i, counter int) {
	if i > counter {
		return
	}
	fmt.Println(i)
	recursion4(i+1, counter)
}

func main() {
	i := 1
	counter := 5
	recursion4(i, counter)
}

*********************
Output
*********************
1
2
3
4
5
package main

import "fmt"

func recursion5(i, counter int) {
	if i < 1 {
		return
	}
	fmt.Println(i)
	recursion5(i-1, counter)
}

func main() {
	counter := 5
	i := counter
	recursion5(i, counter)
}

*********************
Output
*********************
5
4
3
2
1

Backtracking

Logic

  • Here, we need to first do recursion
  • And after recursion call are getting completed from base case, we can perform actual logic. 
package main

import "fmt"

func recursion6(i, counter int) {
  // base case
	if i < 1 {
		return
	}
	
	// recursion call is made
	recursion6(i-1, counter)
	
	// Here logic is performed after recursion call is returned
	fmt.Println(i)
}

func main() {
	counter := 5
	i := counter
	recursion6(i, counter)
}

*********************
Output
*********************
1
2
3
4
5
package main

import "fmt"

func recursion7(i, counter int) {
	if i > counter {
		return
	}
	recursion7(i+1, counter)
	fmt.Println(i)
}

func main() {
	counter := 5
	i := 1
	recursion7(i, counter)
}

*********************
Output
*********************
5
4
3
2
1

Parametrised and Functional Recursion

Parametrized

Problem-1 : Sum of first N numbers using recursion

package main

import "fmt"

func recursion9(i int, sum *int) {
	if i < 1 {
		return
	}

	*sum = *sum + i
	recursion9(i-1, sum)
}

func main() {
	counter := 4
	sum := 0
	recursion9(counter, &sum)
	fmt.Printf("Parametrized : Sum of first %d Numbers is %d\n", counter, sum)
}

*********************
Output
*********************
Parametrized : Sum of first 4 Numbers is 10

Functional

Problem-2: Sum of first N numbers using recursion

package main

import "fmt"

func recursion8(i int) int {
	if i < 1 {
		return 0
	}

	sum := i + recursion8(i-1)
	return sum
}

func main() {
	counter := 3
	sum := recursion8(counter)
	fmt.Printf("Functional : Sum of first %d Numbers is %d\n", counter, sum)
}


*********************
Output
*********************
Functional : Sum of first 3 Numbers is 6

Problem–3. Factorial of first N numbers using recursion

package main

import "fmt"

func fact(i int) int {
	if i < 1 {
		return 1
	}

	ans := i * fact(i-1)
	return ans
}

func main() {
	counter := 4
	fact := fact(counter)
	fmt.Printf("Functional : Factorial of first %d Numbers is %d\n", counter, fact)
}

*********************
Output
*********************
Functional : Factorial of first 4 Numbers is 24

Problem–4.1 Reverse an array using recursion

package main

import "fmt"

func reverse(arr []int, left, right int) {
	if left >= right {
		return
	}

	// swap
	arr[left], arr[right] = arr[right], arr[left]

	// reduce the window
	reverse(arr, left+1, right-1)
}

func main() {
	arr := []int{1, 2, 3, 4, 5}
	left := 0
	right := len(arr) - 1
	reverse(arr, left, right)
	fmt.Printf("After reversing array : %#v\n", arr)
}

*********************
Output
*********************
After reversing array : []int{5, 4, 3, 2, 1}

Problem–4.2 Reverse an array single params

package main

import "fmt"

func reverse_using_single_index(arr []int, left int) {
	n := len(arr)

	if left >= n/2 {
		return
	}

	// swap
	arr[left], arr[n-left-1] = arr[n-left-1], arr[left]

	// reduce the window
	reverse_using_single_index(arr, left+1)
}

func main() {
	arr := []int{1, 2, 3, 4, 5}
	left := 0
	reverse_using_single_index(arr, left)
	fmt.Printf("After reversing array : %#v\n", arr)
}

*********************
Output
*********************
After reversing array : []int{5, 4, 3, 2, 1}

Problem 5 String is Palindrome or not

package main

import "fmt"

func isPalindrome(arr string, left, right int) bool {
	if left >= right {
		return true
	}

	// swap
	if arr[left] != arr[right] {
		return false
	}

	// reduce the window
	return isPalindrome(arr, left+1, right-1)
}

func main() {
	arr := "ABCB"
	left := 0
	right := len(arr) - 1
	answer := isPalindrome(arr, left, right)
	fmt.Printf("String = %s, palindrome = %t \n", arr, answer)
}


*********************
Output
*********************

String = ABCBA is palindrome = true

String = ABCB, palindrome = false

Multiple Recursion calls

Problem 1 Fibonacci number

package main

import "fmt"

func fibo(n int) int {
	if n == 1 {
		return 0
	}

	if n == 2 {
		return 1
	}

	return fibo(n-1) + fibo(n-2)
}

func fiboOptimized(n int, hist map[int]int) int {
	if n == 1 {
		return 0
	}

	if n == 2 {
		return 1
	}

	if _, found := hist[n-1]; !found {
		hist[n-1] = fiboOptimized(n-1, hist)
	}

	if _, found := hist[n-2]; !found {
		hist[n-2] = fiboOptimized(n-2, hist)
	}

	return hist[n-1] + hist[n-2]
}

func main() {
	// Fibonacci sequence
	// 0, 1, 1, 2, 3,
	// 5, 8, 13, 21, 34,
	// 55, 89, 144, 233, 377,
	// 610
	n := 70
	answer := fibo(n)
	fmt.Printf("Basic Fibonacci of %d is %d\n", n, answer)

	hist := make(map[int]int)
	optAnswer := fiboOptimized(n, hist)
	fmt.Printf("Optimized Fibonacci of %d is %d\n", n, optAnswer)

}


*********************
Output
*********************

Basic Fibonacci of 30 is 514229
Optimized Fibonacci of 30 is 514229
Benchmarking Results
// file name : fibonacci_test.go
package main

import "testing"

func BenchmarkFibo(b *testing.B) {
	for i := 0; i < b.N; i++ {
		fibo(40)
	}
}

func BenchmarkFiboOptimized(b *testing.B) {
	for i := 0; i < b.N; i++ {
		hist := make(map[int]int)
		fiboOptimized(40, hist)
	}
}


*********************
Output
*********************

goos: darwin
goarch: arm64
pkg: goexample/recursion1/fibo
BenchmarkFibo-8                        4         250860427 ns/op
BenchmarkFiboOptimized-8          511828              2241 ns/op
PASS
ok      goexample/recursion1/fibo       3.625s

Subsequence using Recursion

What is a Subsequence ?

  • Contiguous or Non-Contiguous sequence which follows the order
  • Ex.
arr = [3, 2, 1]

*********************************************
All Subsequence
*********************************************
{} -- Empty array
3
2
1
3, 2
2, 1
3,2,1
3, 1  -----> This is a subsequence even if it non-contiguous.

Logic

  • We will use Take and Not Take logic on indexes
  • It is similar to creating truth table.
  • In above example we have N places (3) and 2 options to fill place with actual values or skip the place itself.
  • In below section, we have listed down how the various combinations will look like.
3 2 1

Total length = 3
2^3 = 8 combinations

1  _ _ _ -> X X X
2  _ _ _ -> 3 X X
3  _ _ _ -> X 2 X
4  _ _ _ -> X X 1
5  _ _ _ -> 3 2 X
6  _ _ _ -> X 2 1
7  _ _ _ -> 3 2 1
8  _ _ _ -> 3 X 1

Golang Code

package main

import "fmt"

func subSequence(arr []int, index int, current []int, result *[][]int, n int) {
	if index >= len(arr) {
		*result = append(*result, current)
		return
	}

	// pick
	current = append(current, arr[index])
	subSequence(arr, index+1, current, result, n)

	// not pick
	current = current[0 : len(current)-1]
	subSequence(arr, index+1, current, result, n)
}

func main() {
	arr := []int{3, 2, 1}

	result := [][]int{}
	current := []int{}
	n := len(arr)
	startingIndex := 0
	subSequence(arr, startingIndex, current, &result, n)
	for index := range result {
		fmt.Printf("%#v\n", result[index])
	}
}

Output

[]int{3, 2, 1}
[]int{3, 2}
[]int{3, 1}
[]int{3}
[]int{2, 1}
[]int{2}
[]int{1}
[]int{}

Please visit https: https://codeandalgo.com for more such contents.

Leave a Reply

Your email address will not be published. Required fields are marked *