# How to solve this recursion problem?

Page 1 of 1

## 4 Replies - 430 Views - Last Post: 09 February 2016 - 10:50 PM

### #1 DerGiLLster

Reputation: 0
• Posts: 10
• Joined: 24-October 15

# How to solve this recursion problem?

Posted 09 February 2016 - 04:18 PM

I have a recursive function called fun that process a list by repeatedly subdividing and operating on halves of the list by repeatedly subdividing and operating on halves of the list.

The base case is when the function is asked to operate on a function of size 1. It requires performing the step: fun(left) + fun(right). If each function call consumes 100 bytes of memory, how many bytes will be on the activation stack when the function is at it's peak memory consumption for a list of size 8?

I would imagine it being 800 bytes since, it calls upon each size being 100 bytes. Am I interpreting this question right or no? Is the relation between size and bytes off?

Is This A Good Question/Topic? 0

## Replies To: How to solve this recursion problem?

### #2 tlhIn`toq

• Freelance developer

Reputation: 6195
• Posts: 13,675
• Joined: 02-June 10

## Re: How to solve this recursion problem?

Posted 09 February 2016 - 04:28 PM

### #3 DerGiLLster

Reputation: 0
• Posts: 10
• Joined: 24-October 15

## Re: How to solve this recursion problem?

Posted 09 February 2016 - 04:37 PM

No I;m asking if my answer, 800 bytes, is right. If not, what am I doing wrong?

### #4 tlhIn`toq

• Freelance developer

Reputation: 6195
• Posts: 13,675
• Joined: 02-June 10

## Re: How to solve this recursion problem?

Posted 09 February 2016 - 04:46 PM

100 bytes per call
Each call cuts the list in half
The list size is 8
So how many times must the list be cut in half, then each half in half {repeat recursively}? That's the number of times the function is called. Times 100bytes per call.

Its not a straight 8*100bytes. You have to walk through the logical operation to see how many times the function is called.

If nothing else, just write a quick bit of code to walk through it and count the number of times the function is called.

This post has been edited by tlhIn`toq: 09 February 2016 - 04:56 PM

### #5 Skydiver

• Code herder

Reputation: 4782
• Posts: 15,810
• Joined: 05-May 12

## Re: How to solve this recursion problem?

Posted 09 February 2016 - 10:50 PM

Also, the question is not how much memory is used after processing the list.

The question is:

DerGiLLster, on 09 February 2016 - 06:18 PM, said:

how many bytes will be on the activation stack when the function is at it's peak memory consumption for a list of size 8?

Spoiler