算法：了解递归函数

Question

I'm learning Golang and i'm trying to understand the logic behind the output of a recursive function.

Here is my program :

package main 

import(
    "fmt"
)

func rec(i int) (int){
    if i == 5{
        fmt.Println("Break", i)
        return i
    }

    rec(i+1)
    fmt.Println("i = ", i)

    return i
}

func main(){
    j := 0
    j = rec(1)

    fmt.Println("Value j = ", j)

}

The output:

Break 5
i =  4
i =  3
i =  2
i =  1
Value j =  1

My questions are:

Why the first output (break 5) is in the top of outputs? Isn't the last output in my function to be printed ?

And why in the main function

j = rec(1) 

return 1 and ignore the return of the condition ?

if i == 5{ 
        fmt.Println("Break", i)
        return i // Here normally the return will be: return 5 ??
    }

PS: I'm using Go version go1.2.1 linux/386 under Ubuntu 14.04

Thanks for your answers.

Answer 1

This line in the func rec(i int) function

rec(i+1) // recurse at the i+1 value
fmt.Println("i = ", i)

Recursively iterates i until it reaches 5, after which your if condition triggers, which is why 5 is first printed, and then it successively goes down through the call stack, printing 4, then 3, ... etc.

This is a question r.e. recursion, not Go specifically. There are numerous resources to help you understand, here is an explanation of recursion in the Towers of Hanoi problem.