#recursion

41 messages · Page 1 of 1 (latest)

restive zodiac
#

I'm having a ruff time comprehending recursion.

# 
package main
import ("fmt")

func testcount(x int) int {
  if x == 11 {
    return 0
  }
  fmt.Println(x)
  return testcount(x + 1)
}

func main(){
  testcount(2)
}```
#

what exactly does return mean

#

Why those it loop

#

and how does x == 11 act as an exit condition

#

I don't get it

night sinew
#

Recursion can be tough

#

return means "stop executing this function and provide this value to the caller"

night sinew
night sinew
#

Do you have an IDE with a debugger? I recommend walking through the function step by step

#

I'm on the bus rn but can provide more notes once I'm stationary

restive zodiac
#

oh lol

#

I don't have a debugger

restive zodiac
#

I didn't catch that

night sinew
#

testcount has a return type of int

#

So it doesn't return a function at any point

#

return testcount(x + 1) doesn't mean "return the expression testcount(x + 1) to the caller"

#

It means "return the value of evaluating the expression testcount(x + 1) to the caller"

#

Do you understand the difference?

restive zodiac
#

So how does it know

#

which value

#

would exit the loop?

night sinew
#

1sec lemme get off the bus

spark solstice
#

Return exits the function, so if x == 11 you exit the function, and if it isn't, then you call the function again with x+1 instead of x

night sinew
#

answers:

#

what happens when you call testcount(11)?
||the condition x == 11 is satisfied, so the function immediately returns 0||

what happens when you call testcount(10)?
||the condition x == 11 is not satisfied, so the function prints 10 and then calls testcount(11). once testcount(11) is done evaluating, it returns the value||

what happens when you call testcount(9)? etc.

||the condition x == 11 is not satisfied, so the function prints 9 and then calls testcount(10). once testcount(10) is done evaluating, it returns the value||

#

$$test$$

#

no texit 😦

#

let's look at another example: a recursive function to calculate n! (n factorial), which is defined as:

n! = 1 * 2 * 3 * ... * (n - 1) * n

in english, you're counting from 1 to n and multiplying all the numbers together

restive zodiac
#

Explain whathow this line works

#

return testcount(x + 1)

#

I don't get the +1

night sinew
# 
package main

import "fmt"

func factorial(n int) int {
    fmt.Printf("factorial(%v): starting execution\n", n)

    // This is our base condition/exit condition. It is the simplest possible
    // problem, which we can either easily calculate the answer to or we
    // already know the answer to.
    //
    // In this case, 0! = 1 and 0! = 1 by definition of the factorial.
    if n == 0 || n == 1 {
        fmt.Printf("factorial(%v): base condition satisfied! returning 1\n", n)
        return 1
    }

    // This is our recursive step. Recursive steps generally consist of three parts:
    //    1. finding a way to simplify the problem,
    //    2. getting the answer to the simplified problem through a recursive call,
    //    3. using the answer to the simplified problem to determine the answer to
    //        the original, more complex problem.
    //
    // Let's begin with part 1. How can we make our problem simpler? In this case,
    // it's pretty easy, because we can just subtract 1 from n to get a smaller number.
    simplerN := n - 1

    // Onto part 2: let's find the answer to our simpler problem via a recursive call.
    fmt.Printf("factorial(%v): base condition not satisfied! calling factorial(%v)\n", n, simplerN)
    simplerAnswer := factorial(simplerN)
    fmt.Printf("factorial(%v): got %v from factorial(%v)\n", n, simplerAnswer, simplerN)

    // And finally, part 3: let's use simplerAnswer to find the answer to our problem.
    // In this case, it happens that n! = (n-1)! * n. For example:
    // 5! = 1 * 2 * 3 * 4 * 5 = (1 * 2 * 3 * 4) * 5 = 4! * 5
    answer := simplerAnswer * n
    fmt.Printf("factorial(%v): returning %v\n", n, answer)
    return answer
}

func main() {
    n := 5
    res := factorial(5)
    fmt.Printf("%v! = %v\n", n, res)
}
night sinew