CODEWITHSUNDEEP
gorecursion
kenpeter
kenpeter

Reputation: 8294

How to pass an accumulator to a recursive func?

(I'm new to Go.)

I am working on this leetcode problem: https://leetcode.com/problems/pascals-triangle/

package main
import "fmt"

func main() {
    arrRes := [][]int{}
    gen(5, arrRes)
    fmt.Println(arrRes) 
}

func gen(numRows int, arrRes [][]int) { 
    build(numRows, 0, arrRes)
}

func build(n int, level int, arrRes [][]int) {
    if(n == level) {
        return 
    }

    arr := []int{}
    if level == 0 {
        arr = append(arr, 1)
    } else if level == 1 {
        arr = append(arr, 1, 1)
    } else {
        // get it out
        tmp := arrRes[level-1]
        arr = comb(tmp)
    }

    arrRes = append(arrRes, arr)
    build(n, level+1, arrRes)
}

func comb(arr []int) []int{
    // arr type init
    tmpArr := []int{1}
    for i:=1;  i<len(arr); i++ {
        sum := arr[i-1] + arr[i]
        tmpArr = append(tmpArr, sum)    
    }

    // go use val, not ref
    tmpArr = append(tmpArr, 1)
    return tmpArr;
}

I want to define an accumulated variable arrRes := [][]int{} and keep passing into the recursive function. I think Go is pass-by-value instead of pass-by-reference. Is there a way to keep this pattern?

I've got two alternative methods:

  1. passing a global var.

  2. pass a 2D array into the func then return the new 2D array.

https://github.com/kenpeter/go_tri/blob/master/tri_global.go

https://github.com/kenpeter/go_tri/blob/master/tri.go

Upvotes: 0

Views: 1160

Answers (1)

jrefior
jrefior

Reputation: 4431

A slice is (basically) three things: a length, a capacity, and a pointer to an underlying array. Everything in Go is pass-by-value, so when you pass a slice to a function you are passing its current length, current capacity, and the memory address of the pointer. Changes made to length and capacity inside the function are made to a copy, and will not affect the length and capacity of the slice that was passed as an argument in the function call.

Printing a slice doesn't print its underlying array, it prints the part of the underlying array that is visible in the slice (which could be none of it if len = 0), based on (1) the pointer to the first element in the underlying array that's supposed to be visible to the slice; and (2) the length in the slice variable.

If you are modifying the length or capacity of a slice inside a function and you want those changes to be visible outside the function, you can either return the slice to update the context outside the function, like append does:

numbers := append(numbers, 27)

Or you can pass in a pointer to a slice:

func ChangeNumbersLenOrCap(numbers *[]int) {
    // make your changes, no return value required
}

For your program, it looks like you could get away with a pointer to a slice of int slices:

var arrRes *[][]int

...because you're not modifying the int slice across another function boundary. Some programs would need a pointer to a slice of pointers to int slices:

var arrRes *[]*[]int

Here are some simple edits to get you started:

    arrRes := [][]int{}
    gen(5, &arrRes)
    fmt.Println(arrRes) 
}

func gen(numRows int, arrRes *[][]int) { 

// ...

func build(n int, level int, arrRes *[][]int) {

     // ...

          tmp := *arrRes[level-1]

     // ...

     *arrRes = append(*arrRes, arr)
     build(n, level+1, arrRes)

Upvotes: 3

Related Questions