Why Recursion Exists and What Loops Cannot Express Cleanly in DSA Go - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to call the recursive function correctly.

DSA Go

func factorial(n int) int {
    if n == 0 {
        return 1
    }
    return n * factorial([1])
}

Drag options to blanks, or click blank then click option'

An+1

Bn-1

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n+1 causes infinite recursion.

Using 0 or 1 directly breaks the recursion logic.

The factorial function calls itself with n-1 to reduce the problem size step by step.

2fill in blank

medium

Complete the code to check the base case in recursion.

DSA Go

func sumToN(n int) int {
    if [1] {
        return 0
    }
    return n + sumToN(n-1)
}

Drag options to blanks, or click blank then click option'

An == 1

Bn < 0

Cn >= 0

Dn <= 0

Attempts:

3 left

💡 Hint

Common Mistakes

Using n == 1 misses zero case.

Using n >= 0 never stops recursion.

Using n < 0 misses zero case.

The base case stops recursion when n is zero or less, returning 0.

3fill in blank

hard

Fix the error in the recursive Fibonacci function call.

DSA Go

func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacci([1]) + fibonacci(n-2)
}

Drag options to blanks, or click blank then click option'

An+1

Bn-2

Cn-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n-2 twice misses the n-1 term.

Using n+1 causes infinite recursion.

Using 1 breaks the sequence.

The Fibonacci function calls itself with n-1 and n-2 to sum previous two numbers.

4fill in blank

hard

Fill both blanks to create a recursive function that prints numbers from n down to 1.

DSA Go

func printDown(n int) {
    if n [1] 0 {
        return
    }
    fmt.Println(n)
    printDown([2])
}

Drag options to blanks, or click blank then click option'

A<=

B>=

Cn-1

Dn+1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n >= 0 causes infinite recursion.

Using n+1 increases n causing infinite recursion.

The function stops when n is less or equal to 0 and calls itself with n-1 to count down.

5fill in blank

hard

Fill all three blanks to create a recursive function that computes the sum of elements in a slice.

DSA Go

func sumSlice(nums []int) int {
    if len(nums) [1] 0 {
        return 0
    }
    return nums[0] + sumSlice(nums[[2]:[3]])
}

Drag options to blanks, or click blank then click option'

A==

B1

Clen(nums)

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using != instead of == in base case causes infinite recursion.

Using wrong slice indices causes runtime errors.

The base case checks if slice length is zero. The recursive call sums first element plus sum of the rest slice from index 1 to end.

Practice

1. Why do we use recursion instead of loops in some problems?

easy

A. Because recursion always uses less memory than loops

B. Because loops are slower than recursion in all cases

C. Because recursion can express problems with self-similar structure more naturally

D. Because loops cannot perform repeated actions

Solution

1. Step 1: Understand recursion's purpose

   Recursion is useful when a problem can be broken down into smaller versions of itself, like tree traversal or factorial calculation.

2. Step 2: Compare recursion and loops

   Loops repeat actions but do not naturally express self-similar or nested structures, which recursion handles clearly.

3. Final Answer:

   Because recursion can express problems with self-similar structure more naturally -> Option C

4. Quick Check:

   Recursion = natural for self-similar problems [OK]

Hint: Recursion fits problems with repeated smaller subproblems [OK]

Common Mistakes:

• Thinking loops are always faster
• Believing recursion always uses less memory
• Assuming loops cannot repeat actions

2. Which of the following is the correct syntax for a recursive function in Go?

easy

A. func factorial(n int) int { if n == 0 { return 1 } else { return n * factorial(n-1) } }

B. func factorial(n int) { if n == 0 { return 1 } else { return n * factorial(n-1) } }

C. func factorial(n int) int { for n > 0 { return n * factorial(n-1) } return 1 }

D. func factorial(n int) int { if n == 0 { return 0 } else { return n * factorial(n-1) } }

Solution

1. Step 1: Check function return type and base case

   func factorial(n int) int { if n == 0 { return 1 } else { return n * factorial(n-1) } } correctly defines a function returning int and has a base case returning 1 when n == 0.

2. Step 2: Verify recursive call and return statement

   func factorial(n int) int { if n == 0 { return 1 } else { return n * factorial(n-1) } } correctly returns n multiplied by factorial(n-1), matching factorial definition.

3. Final Answer:

   func factorial(n int) int { if n == 0 { return 1 } else { return n * factorial(n-1) } } -> Option A

4. Quick Check:

   Correct recursive syntax = func factorial(n int) int { if n == 0 { return 1 } else { return n * factorial(n-1) } } [OK]

Hint: Look for base case and correct return type in recursion [OK]

Common Mistakes:

• Missing return type in function signature
• Returning wrong base case value
• Using loops instead of recursion incorrectly

3. What is the output of this Go code?

func sum(n int) int {
    if n == 0 {
        return 0
    }
    return n + sum(n-1)
}

func main() {
    fmt.Println(sum(3))
}

medium

A. Error: undefined fmt

B. 3

C. 0

D. 6

Solution

1. Step 1: Analyze the sum function logic

   The sum function recursively adds numbers from n down to 0, so sum(3) = 3 + 2 + 1 + 0 = 6.

2. Step 2: Check code completeness and imports

   The code uses fmt.Println but does not import "fmt", causing a compile error.

3. Final Answer:

   Error: undefined fmt -> Option A

4. Quick Check:

   Missing import causes error = Error: undefined fmt [OK]

Hint: Check for missing imports before output [OK]

Common Mistakes:

• Assuming output is 6 without checking imports
• Ignoring compile errors
• Confusing recursion base case

4. Identify the error in this recursive Go function and fix it:

func countdown(n int) {
    if n == 0 {
        fmt.Println("Done")
    }
    fmt.Println(n)
    countdown(n-1)
}

medium

A. Function should return int instead of void

B. Missing else causes infinite recursion when n == 0

C. Base case should print n instead of "Done"

D. No error, function works correctly

Solution

1. Step 1: Analyze base case and recursion call

   When n == 0, it prints "Done" but then continues to print 0 and calls countdown(-1), causing infinite recursion.

2. Step 2: Fix by adding else to stop recursion after base case

   Adding else before printing n and calling countdown(n-1) stops recursion at zero.

3. Final Answer:

   Missing else causes infinite recursion when n == 0 -> Option B

4. Quick Check:

   Base case must stop recursion [OK]

Hint: Ensure base case stops recursion with else or return [OK]

Common Mistakes:

• Not stopping recursion at base case
• Printing after base case without condition
• Changing return type unnecessarily

5. You want to print all paths from root to leaves in a tree structure. Why is recursion better than loops for this task?

hard

A. Because loops always cause infinite loops in trees

B. Because loops cannot traverse trees at all

C. Because recursion uses less memory than loops for trees

D. Because recursion naturally handles branching and backtracking without complex stack management

Solution

1. Step 1: Understand tree traversal complexity

   Tree traversal requires exploring branches and returning to previous nodes, which recursion handles by call stack automatically.

2. Step 2: Compare recursion and loops for branching

   Loops need explicit stack or queue to track nodes, making code complex; recursion simplifies this by implicit call stack.

3. Final Answer:

   Because recursion naturally handles branching and backtracking without complex stack management -> Option D

4. Quick Check:

   Recursion = natural for branching structures [OK]

Hint: Recursion handles branching and backtracking simply [OK]

Common Mistakes:

• Thinking loops cannot traverse trees
• Assuming recursion always uses less memory
• Believing loops cause infinite loops in trees