CODEWITHSUNDEEP
recursiongo
user2671513
user2671513

Reputation:

Recursion, and not ending the recursion by return statement

I am doing binary search in this tree and expect the Find recursion to end when the result is true. It does have a result of true but even if it gets the true value and runs the return statement, it seems like continue to run and finally reach the value of false

How do I make this program end when it finds the value and returns?

http://play.golang.org/p/miWqRVo_XO

package main

import "fmt"

type Tree struct {
  Left  *Tree
  Value int64
  Right *Tree
}

func NewT(val int64) *Tree {
  return &Tree{
    Left:  new(Tree),
    Value: val,
    Right: new(Tree),
  }
}

func (T *Tree) Insert(val int64) *Tree {
  if T == nil {
    return &Tree{nil, val, nil}
  }
  if val < T.Value {
    T.Left = T.Left.Insert(val)
  } else {
    T.Right = T.Right.Insert(val)
  }
  return T
}

func (T *Tree) Find(val int64) bool {
  fmt.Printf("%v , %v\n", T.Value, val)
  fmt.Printf("%v\n", T.Value == val)

  if fmt.Sprintf("%v", T.Value) == fmt.Sprintf("%v", val) {
    fmt.Println("True and we do return true")
    return true
  }
  if val < T.Value {
    T.Left.Find(val)
  } else {
    T.Right.Find(val)
  }
  fmt.Println("False")
  return false
}

func main() {
  t1 := NewT(5)
  for i := 0; i < 10; i++ {
    t1 = t1.Insert(int64(i))
  }
  fmt.Println("Result:", t1.Find(7))
}

Output is 

5 , 7
false
0 , 7
false
5 , 7
false
6 , 7
false
7 , 7
true
True and we do return true

Upvotes: 2

Views: 85

Answers (1)

James Henstridge
James Henstridge

Reputation: 43949

You seem to be ignoring the return value of Tree.Find when you recurse into it. If you pass on the return value, you should get the desired behaviour. That is, modify the end of Find to read:

if val < T.Value {
    return T.Left.Find(val)
} else {
    return T.Right.Find(val)
}

Upvotes: 4

Related Questions