Различные типы рекурсии на Голанге

Опубликовано: 9 Января, 2022

Рекурсия - это концепция, при которой функция вызывает себя прямым или косвенным образом. Каждый вызов рекурсивной функции - это уменьшенная версия, поэтому в какой-то момент она сходится. Каждая рекурсивная функция имеет базовый вариант или базовое условие, которое является последним исполняемым оператором в рекурсии и останавливает дальнейшие вызовы.

Существуют различные типы рекурсии, как описано в следующих примерах:

1. Прямая рекурсия

Тип рекурсии, при которой функция вызывает себя напрямую, без помощи другой функции, называется прямой рекурсией. Следующий пример объясняет концепцию прямой рекурсии:

Example:

// Golang program to illustrate the
// concept of direct recursion
package main
  
import (
    "fmt"
)
  
// recursive function for 
// calculating a factorial 
// of a positive integer
func factorial_calc(number int) int {
  
    // this is the base condition
    // if number is 0 or 1 the
    // function will return 1
    if number == 0 || number == 1 {
        return 1
    }
      
    // if negative argument is 
    // given, it prints error
    // message and returns -1
    if number < 0 {
        fmt.Println("Invalid number")
        return -1
    }
      
    // recursive call to itself
    // with argument decremented 
    // by 1 integer so that it
    // eventually reaches the base case
    return number*factorial_calc(number - 1)
}
  
// the main function
func main() {
  
    // passing 0 as a parameter
    answer1 := factorial_calc(0)
    fmt.Println(answer1, "
")
      
    // passing a positive integer
    answer2 := factorial_calc(5)
    fmt.Println(answer2, "
")
      
    // passing a negative integer
    // prints an error message
    // with a return value of -1
    answer3 := factorial_calc(-1)
    fmt.Println(answer3, "
")
      
    // passing a positive integer
    answer4 := factorial_calc(10)
    fmt.Println(answer4, "
")
}

Выход:

1 

120 

Invalid number
-1 

3628800

2. Косвенная рекурсия

Тип рекурсии, при которой функция вызывает другую функцию, а эта функция, в свою очередь, вызывает вызывающую функцию, называется косвенной рекурсией. Этот тип рекурсии использует другую функцию. Функция вызывает саму себя, но косвенно, то есть через другую функцию. В следующем примере объясняется концепция косвенной рекурсии:

Example:

// Golang program to illustrate the
// concept of indirect recursion
package main
  
import (
    "fmt"
)
  
// recursive function for 
// printing all numbers 
// upto the number n
func print_one(n int) {
      
    // if the number is positive
    // print the number and call 
    // the second function
    if n >= 0 {
        fmt.Println("In first function:", n)
        // call to the second function
        // which calls this first
        // function indirectly
        print_two(n - 1)
    }
}
  
func print_two(n int) {
  
    // if the number is positive
    // print the number and call 
    // the second function
    if n >= 0 {
        fmt.Println("In second function:", n)
        // call to the first function
        print_one(n - 1)
    }
}
  
// main function
func main() {
      
    // passing a positive 
    // parameter which prints all 
    // numbers from 1 - 10
    print_one(10)
      
    // this will not print
    // anything as it does not
    // follow the base case
    print_one(-1)
}

Выход:

В первой функции: 10
Во второй функции: 9
В первой функции: 8
Во второй функции: 7
В первой функции: 6
Во второй функции: 5
В первой функции: 4
Во второй функции: 3
В первой функции: 2
Во второй функции: 1
В первой функции: 0

Примечание: косвенная рекурсия только с 2 функциями называется взаимной рекурсией. Для косвенной рекурсии может быть более двух функций.

3. Рекурсия хвоста

Хвостовой вызов - это вызов подпрограммы, который является последним или последним вызовом функции. Когда хвостовой вызов выполняет вызов той же функции, функция называется хвостовой рекурсивной. Здесь рекурсивный вызов - это последнее, что выполняет функция.

Example:

// Golang program to illustrate the
// concept of tail recursion
package main
  
import (
    "fmt"
)
  
// tail recursive function
// to print all numbers 
// from n to 1
func print_num(n int) {
      
    // if number is still 
    // positive, print it
    // and call the function
    // with decremented value
    if n > 0 {
        fmt.Println(n)
          
        // last statement in 
        // the recursive function
        // tail recursive call
        print_num(n-1)
    }
}
  
// main function
func main() {
      
    // passing a positive 
    // number, prints 5 to 1
    print_num(5)
}

Выход:

4. Рекурсия головы.

В головной рекурсии рекурсивный вызов является первым оператором функции. Перед вызовом нет других операторов или операций. Функция не должна ничего обрабатывать во время вызова, и все операции выполняются во время возврата.

Example:

// Golang program to illustrate the
// concept of head recursion
package main
  
import (
    "fmt"
)
  
// head recursive function
// to print all numbers 
// from 1 to n
func print_num(n int) {
      
    // if number is still 
    // less than n, call 
    // the function
    // with decremented value
    if n > 0 {
          
        // first statement in 
        // the function
        print_num(n-1)
          
        // printing is done at
        // returning time
        fmt.Println(n)
    }
}
  
// main function
func main() {
      
    // passing a positive 
    // number, prints 5 to 1
    print_num(5)
}

Выход:

Примечание: вывод головной рекурсии в точности противоположен выводу хвостовой рекурсии. Это связано с тем, что хвостовая рекурсия сначала печатает число, а затем вызывает себя, тогда как в головной рекурсии функция продолжает вызывать себя до тех пор, пока не достигнет базового случая, а затем начинает печать во время возврата.

5. Бесконечная рекурсия

Все рекурсивные функции были определенными или конечными рекурсивными функциями, т. Е. Они останавливались при достижении базового условия. Бесконечная рекурсия - это тип рекурсии, которая продолжается до бесконечности и никогда не сходится к базовому случаю. Это часто приводит к сбою системы или переполнению памяти.

Example:

// Golang program to illustrate the
// concept of infinite recursion
package main
  
import (
    "fmt"
)
  
// infinite recursion function
func print_hello() {
      
    // printing infinite times
    fmt.Println("GeeksforGeeks")
    print_hello()
}
  
// main function
func main() {
      
    // call to infinite 
    // recursive function
    print_hello()
}

Выход:

GeeksforGeeks
GeeksforGeeks
GeeksforGeeks
..... бесконечное количество раз

6. Рекурсия анонимной функции

В Голанге существует концепция функций, не имеющих имени. Такие функции называются анонимными функциями. Рекурсия также может выполняться с использованием анонимных функций в Golang, как показано ниже:

Example:

// Golang program to illustrate 
// the concept of anonymous 
// function recursion
package main
  
import (
    "fmt"
)
  
// main function
func main() {
      
    // declaring anonymous function
    // that takes an integer value
        var anon_func func(int)
           
    // defining an anonymous
    // function that prints
    // numbers from n to 1
        anon_func = func(number int) {
      
        // base case
            if number == 0 {
                    return 
            } else {
            fmt.Println(number)
              
            // calling anonymous 
            // function recursively
                    anon_func(number-1)
            }
        }
      
    // call to anonymous 
    // recursive function
        anon_func(5)
}

Выход:

Go язык

Различные типы рекурсии на Голанге

1. Прямая рекурсия

2. Косвенная рекурсия

3. Рекурсия хвоста

4. Рекурсия головы.

5. Бесконечная рекурсия

6. Рекурсия анонимной функции

РЕКОМЕНДУЕМЫЕ СТАТЬИ