Algorithm: Understanding recursive function

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.

Community · Accepted Answer · 2017-05-23 12:02:22Z

3

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.

edited May 23, 2017 at 12:02

CommunityBot

11 silver badge

answered Jul 9, 2016 at 14:08

ifma

3,8584 gold badges30 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ifma Over a year ago

@nexus66 Because your function recursively returns 5, then 4, then 3... etc. So your j variable was equal to 5 at first, then it gets overwritten to 4, then 3, ..., until it hits 1, which you print.

Chiheb Nexus Over a year ago

Thanks ! I got the logic behind.

Collectives™ on Stack Overflow

Algorithm: Understanding recursive function

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related